001/* 002 * Copyright (C) 2008 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; 020import static java.util.Objects.requireNonNull; 021 022import com.google.common.annotations.GwtCompatible; 023import com.google.common.annotations.GwtIncompatible; 024import com.google.common.annotations.VisibleForTesting; 025import com.google.errorprone.annotations.CanIgnoreReturnValue; 026import com.google.errorprone.annotations.DoNotCall; 027import com.google.errorprone.annotations.concurrent.LazyInit; 028import com.google.j2objc.annotations.WeakOuter; 029import java.io.Serializable; 030import java.util.Arrays; 031import java.util.Collection; 032import java.util.Collections; 033import java.util.Iterator; 034import java.util.List; 035import java.util.function.Function; 036import java.util.function.ToIntFunction; 037import java.util.stream.Collector; 038import javax.annotation.CheckForNull; 039import org.checkerframework.checker.nullness.qual.Nullable; 040 041/** 042 * A {@link Multiset} whose contents will never change, with many other important properties 043 * detailed at {@link ImmutableCollection}. 044 * 045 * <p><b>Grouped iteration.</b> In all current implementations, duplicate elements always appear 046 * consecutively when iterating. Elements iterate in order by the <i>first</i> appearance of that 047 * element when the multiset was created. 048 * 049 * <p>See the Guava User Guide article on <a href= 050 * "https://github.com/google/guava/wiki/ImmutableCollectionsExplained">immutable collections</a>. 051 * 052 * @author Jared Levy 053 * @author Louis Wasserman 054 * @since 2.0 055 */ 056@GwtCompatible(serializable = true, emulated = true) 057@SuppressWarnings("serial") // we're overriding default serialization 058@ElementTypesAreNonnullByDefault 059public abstract class ImmutableMultiset<E> extends ImmutableMultisetGwtSerializationDependencies<E> 060 implements Multiset<E> { 061 062 /** 063 * Returns a {@code Collector} that accumulates the input elements into a new {@code 064 * ImmutableMultiset}. Elements iterate in order by the <i>first</i> appearance of that element in 065 * encounter order. 066 * 067 * @since 21.0 068 */ 069 public static <E> Collector<E, ?, ImmutableMultiset<E>> toImmutableMultiset() { 070 return CollectCollectors.toImmutableMultiset(Function.identity(), e -> 1); 071 } 072 073 /** 074 * Returns a {@code Collector} that accumulates elements into an {@code ImmutableMultiset} whose 075 * elements are the result of applying {@code elementFunction} to the inputs, with counts equal to 076 * the result of applying {@code countFunction} to the inputs. 077 * 078 * <p>If the mapped elements contain duplicates (according to {@link Object#equals}), the first 079 * occurrence in encounter order appears in the resulting multiset, with count equal to the sum of 080 * the outputs of {@code countFunction.applyAsInt(t)} for each {@code t} mapped to that element. 081 * 082 * @since 22.0 083 */ 084 public static <T extends @Nullable Object, E> 085 Collector<T, ?, ImmutableMultiset<E>> toImmutableMultiset( 086 Function<? super T, ? extends E> elementFunction, 087 ToIntFunction<? super T> countFunction) { 088 return CollectCollectors.toImmutableMultiset(elementFunction, countFunction); 089 } 090 091 /** 092 * Returns the empty immutable multiset. 093 * 094 * <p><b>Performance note:</b> the instance returned is a singleton. 095 */ 096 @SuppressWarnings("unchecked") // all supported methods are covariant 097 public static <E> ImmutableMultiset<E> of() { 098 return (ImmutableMultiset<E>) RegularImmutableMultiset.EMPTY; 099 } 100 101 /** 102 * Returns an immutable multiset containing a single element. 103 * 104 * @throws NullPointerException if {@code element} is null 105 * @since 6.0 (source-compatible since 2.0) 106 */ 107 public static <E> ImmutableMultiset<E> of(E element) { 108 return copyFromElements(element); 109 } 110 111 /** 112 * Returns an immutable multiset containing the given elements, in order. 113 * 114 * @throws NullPointerException if any element is null 115 * @since 6.0 (source-compatible since 2.0) 116 */ 117 public static <E> ImmutableMultiset<E> of(E e1, E e2) { 118 return copyFromElements(e1, e2); 119 } 120 121 /** 122 * Returns an immutable multiset containing the given elements, in the "grouped iteration order" 123 * described in the class documentation. 124 * 125 * @throws NullPointerException if any element is null 126 * @since 6.0 (source-compatible since 2.0) 127 */ 128 public static <E> ImmutableMultiset<E> of(E e1, E e2, E e3) { 129 return copyFromElements(e1, e2, e3); 130 } 131 132 /** 133 * Returns an immutable multiset containing the given elements, in the "grouped iteration order" 134 * described in the class documentation. 135 * 136 * @throws NullPointerException if any element is null 137 * @since 6.0 (source-compatible since 2.0) 138 */ 139 public static <E> ImmutableMultiset<E> of(E e1, E e2, E e3, E e4) { 140 return copyFromElements(e1, e2, e3, e4); 141 } 142 143 /** 144 * Returns an immutable multiset containing the given elements, in the "grouped iteration order" 145 * described in the class documentation. 146 * 147 * @throws NullPointerException if any element is null 148 * @since 6.0 (source-compatible since 2.0) 149 */ 150 public static <E> ImmutableMultiset<E> of(E e1, E e2, E e3, E e4, E e5) { 151 return copyFromElements(e1, e2, e3, e4, e5); 152 } 153 154 /** 155 * Returns an immutable multiset containing the given elements, in the "grouped iteration order" 156 * described in the class documentation. 157 * 158 * @throws NullPointerException if any element is null 159 * @since 6.0 (source-compatible since 2.0) 160 */ 161 public static <E> ImmutableMultiset<E> of(E e1, E e2, E e3, E e4, E e5, E e6, E... others) { 162 return new Builder<E>().add(e1).add(e2).add(e3).add(e4).add(e5).add(e6).add(others).build(); 163 } 164 165 /** 166 * Returns an immutable multiset containing the given elements, in the "grouped iteration order" 167 * described in the class documentation. 168 * 169 * @throws NullPointerException if any of {@code elements} is null 170 * @since 6.0 171 */ 172 public static <E> ImmutableMultiset<E> copyOf(E[] elements) { 173 return copyFromElements(elements); 174 } 175 176 /** 177 * Returns an immutable multiset containing the given elements, in the "grouped iteration order" 178 * described in the class documentation. 179 * 180 * @throws NullPointerException if any of {@code elements} is null 181 */ 182 public static <E> ImmutableMultiset<E> copyOf(Iterable<? extends E> elements) { 183 if (elements instanceof ImmutableMultiset) { 184 @SuppressWarnings("unchecked") // all supported methods are covariant 185 ImmutableMultiset<E> result = (ImmutableMultiset<E>) elements; 186 if (!result.isPartialView()) { 187 return result; 188 } 189 } 190 191 Multiset<? extends E> multiset = 192 (elements instanceof Multiset) 193 ? Multisets.cast(elements) 194 : LinkedHashMultiset.create(elements); 195 196 return copyFromEntries(multiset.entrySet()); 197 } 198 199 /** 200 * Returns an immutable multiset containing the given elements, in the "grouped iteration order" 201 * described in the class documentation. 202 * 203 * @throws NullPointerException if any of {@code elements} is null 204 */ 205 public static <E> ImmutableMultiset<E> copyOf(Iterator<? extends E> elements) { 206 Multiset<E> multiset = LinkedHashMultiset.create(); 207 Iterators.addAll(multiset, elements); 208 return copyFromEntries(multiset.entrySet()); 209 } 210 211 private static <E> ImmutableMultiset<E> copyFromElements(E... elements) { 212 Multiset<E> multiset = LinkedHashMultiset.create(); 213 Collections.addAll(multiset, elements); 214 return copyFromEntries(multiset.entrySet()); 215 } 216 217 static <E> ImmutableMultiset<E> copyFromEntries( 218 Collection<? extends Entry<? extends E>> entries) { 219 if (entries.isEmpty()) { 220 return of(); 221 } else { 222 return RegularImmutableMultiset.create(entries); 223 } 224 } 225 226 ImmutableMultiset() {} 227 228 @Override 229 public UnmodifiableIterator<E> iterator() { 230 final Iterator<Entry<E>> entryIterator = entrySet().iterator(); 231 return new UnmodifiableIterator<E>() { 232 int remaining; 233 @CheckForNull E element; 234 235 @Override 236 public boolean hasNext() { 237 return (remaining > 0) || entryIterator.hasNext(); 238 } 239 240 @Override 241 public E next() { 242 if (remaining <= 0) { 243 Entry<E> entry = entryIterator.next(); 244 element = entry.getElement(); 245 remaining = entry.getCount(); 246 } 247 remaining--; 248 /* 249 * requireNonNull is safe because `remaining` starts at 0, forcing us to initialize 250 * `element` above. After that, we never clear it. 251 */ 252 return requireNonNull(element); 253 } 254 }; 255 } 256 257 @LazyInit @CheckForNull private transient ImmutableList<E> asList; 258 259 @Override 260 public ImmutableList<E> asList() { 261 ImmutableList<E> result = asList; 262 return (result == null) ? asList = super.asList() : result; 263 } 264 265 @Override 266 public boolean contains(@CheckForNull Object object) { 267 return count(object) > 0; 268 } 269 270 /** 271 * Guaranteed to throw an exception and leave the collection unmodified. 272 * 273 * @throws UnsupportedOperationException always 274 * @deprecated Unsupported operation. 275 */ 276 @CanIgnoreReturnValue 277 @Deprecated 278 @Override 279 @DoNotCall("Always throws UnsupportedOperationException") 280 public final int add(E element, int occurrences) { 281 throw new UnsupportedOperationException(); 282 } 283 284 /** 285 * Guaranteed to throw an exception and leave the collection unmodified. 286 * 287 * @throws UnsupportedOperationException always 288 * @deprecated Unsupported operation. 289 */ 290 @CanIgnoreReturnValue 291 @Deprecated 292 @Override 293 @DoNotCall("Always throws UnsupportedOperationException") 294 public final int remove(@CheckForNull Object element, int occurrences) { 295 throw new UnsupportedOperationException(); 296 } 297 298 /** 299 * Guaranteed to throw an exception and leave the collection unmodified. 300 * 301 * @throws UnsupportedOperationException always 302 * @deprecated Unsupported operation. 303 */ 304 @CanIgnoreReturnValue 305 @Deprecated 306 @Override 307 @DoNotCall("Always throws UnsupportedOperationException") 308 public final int setCount(E element, int count) { 309 throw new UnsupportedOperationException(); 310 } 311 312 /** 313 * Guaranteed to throw an exception and leave the collection unmodified. 314 * 315 * @throws UnsupportedOperationException always 316 * @deprecated Unsupported operation. 317 */ 318 @CanIgnoreReturnValue 319 @Deprecated 320 @Override 321 @DoNotCall("Always throws UnsupportedOperationException") 322 public final boolean setCount(E element, int oldCount, int newCount) { 323 throw new UnsupportedOperationException(); 324 } 325 326 @GwtIncompatible // not present in emulated superclass 327 @Override 328 int copyIntoArray(@Nullable Object[] dst, int offset) { 329 for (Multiset.Entry<E> entry : entrySet()) { 330 Arrays.fill(dst, offset, offset + entry.getCount(), entry.getElement()); 331 offset += entry.getCount(); 332 } 333 return offset; 334 } 335 336 @Override 337 public boolean equals(@CheckForNull Object object) { 338 return Multisets.equalsImpl(this, object); 339 } 340 341 @Override 342 public int hashCode() { 343 return Sets.hashCodeImpl(entrySet()); 344 } 345 346 @Override 347 public String toString() { 348 return entrySet().toString(); 349 } 350 351 /** @since 21.0 (present with return type {@code Set} since 2.0) */ 352 @Override 353 public abstract ImmutableSet<E> elementSet(); 354 355 @LazyInit @CheckForNull private transient ImmutableSet<Entry<E>> entrySet; 356 357 @Override 358 public ImmutableSet<Entry<E>> entrySet() { 359 ImmutableSet<Entry<E>> es = entrySet; 360 return (es == null) ? (entrySet = createEntrySet()) : es; 361 } 362 363 private ImmutableSet<Entry<E>> createEntrySet() { 364 return isEmpty() ? ImmutableSet.<Entry<E>>of() : new EntrySet(); 365 } 366 367 abstract Entry<E> getEntry(int index); 368 369 @WeakOuter 370 private final class EntrySet extends IndexedImmutableSet<Entry<E>> { 371 @Override 372 boolean isPartialView() { 373 return ImmutableMultiset.this.isPartialView(); 374 } 375 376 @Override 377 Entry<E> get(int index) { 378 return getEntry(index); 379 } 380 381 @Override 382 public int size() { 383 return elementSet().size(); 384 } 385 386 @Override 387 public boolean contains(@CheckForNull Object o) { 388 if (o instanceof Entry) { 389 Entry<?> entry = (Entry<?>) o; 390 if (entry.getCount() <= 0) { 391 return false; 392 } 393 int count = count(entry.getElement()); 394 return count == entry.getCount(); 395 } 396 return false; 397 } 398 399 @Override 400 public int hashCode() { 401 return ImmutableMultiset.this.hashCode(); 402 } 403 404 @GwtIncompatible 405 @Override 406 Object writeReplace() { 407 return new EntrySetSerializedForm<E>(ImmutableMultiset.this); 408 } 409 410 private static final long serialVersionUID = 0; 411 } 412 413 @GwtIncompatible 414 static class EntrySetSerializedForm<E> implements Serializable { 415 final ImmutableMultiset<E> multiset; 416 417 EntrySetSerializedForm(ImmutableMultiset<E> multiset) { 418 this.multiset = multiset; 419 } 420 421 Object readResolve() { 422 return multiset.entrySet(); 423 } 424 } 425 426 @GwtIncompatible 427 @Override 428 Object writeReplace() { 429 return new SerializedForm(this); 430 } 431 432 /** 433 * Returns a new builder. The generated builder is equivalent to the builder created by the {@link 434 * Builder} constructor. 435 */ 436 public static <E> Builder<E> builder() { 437 return new Builder<E>(); 438 } 439 440 /** 441 * A builder for creating immutable multiset instances, especially {@code public static final} 442 * multisets ("constant multisets"). Example: 443 * 444 * <pre>{@code 445 * public static final ImmutableMultiset<Bean> BEANS = 446 * new ImmutableMultiset.Builder<Bean>() 447 * .addCopies(Bean.COCOA, 4) 448 * .addCopies(Bean.GARDEN, 6) 449 * .addCopies(Bean.RED, 8) 450 * .addCopies(Bean.BLACK_EYED, 10) 451 * .build(); 452 * }</pre> 453 * 454 * <p>Builder instances can be reused; it is safe to call {@link #build} multiple times to build 455 * multiple multisets in series. 456 * 457 * @since 2.0 458 */ 459 public static class Builder<E> extends ImmutableCollection.Builder<E> { 460 final Multiset<E> contents; 461 462 /** 463 * Creates a new builder. The returned builder is equivalent to the builder generated by {@link 464 * ImmutableMultiset#builder}. 465 */ 466 public Builder() { 467 this(LinkedHashMultiset.<E>create()); 468 } 469 470 Builder(Multiset<E> contents) { 471 this.contents = contents; 472 } 473 474 /** 475 * Adds {@code element} to the {@code ImmutableMultiset}. 476 * 477 * @param element the element to add 478 * @return this {@code Builder} object 479 * @throws NullPointerException if {@code element} is null 480 */ 481 @CanIgnoreReturnValue 482 @Override 483 public Builder<E> add(E element) { 484 contents.add(checkNotNull(element)); 485 return this; 486 } 487 488 /** 489 * Adds each element of {@code elements} to the {@code ImmutableMultiset}. 490 * 491 * @param elements the elements to add 492 * @return this {@code Builder} object 493 * @throws NullPointerException if {@code elements} is null or contains a null element 494 */ 495 @CanIgnoreReturnValue 496 @Override 497 public Builder<E> add(E... elements) { 498 super.add(elements); 499 return this; 500 } 501 502 /** 503 * Adds a number of occurrences of an element to this {@code ImmutableMultiset}. 504 * 505 * @param element the element to add 506 * @param occurrences the number of occurrences of the element to add. May be zero, in which 507 * case no change will be made. 508 * @return this {@code Builder} object 509 * @throws NullPointerException if {@code element} is null 510 * @throws IllegalArgumentException if {@code occurrences} is negative, or if this operation 511 * would result in more than {@link Integer#MAX_VALUE} occurrences of the element 512 */ 513 @CanIgnoreReturnValue 514 public Builder<E> addCopies(E element, int occurrences) { 515 contents.add(checkNotNull(element), occurrences); 516 return this; 517 } 518 519 /** 520 * Adds or removes the necessary occurrences of an element such that the element attains the 521 * desired count. 522 * 523 * @param element the element to add or remove occurrences of 524 * @param count the desired count of the element in this multiset 525 * @return this {@code Builder} object 526 * @throws NullPointerException if {@code element} is null 527 * @throws IllegalArgumentException if {@code count} is negative 528 */ 529 @CanIgnoreReturnValue 530 public Builder<E> setCount(E element, int count) { 531 contents.setCount(checkNotNull(element), count); 532 return this; 533 } 534 535 /** 536 * Adds each element of {@code elements} to the {@code ImmutableMultiset}. 537 * 538 * @param elements the {@code Iterable} to add to the {@code ImmutableMultiset} 539 * @return this {@code Builder} object 540 * @throws NullPointerException if {@code elements} is null or contains a null element 541 */ 542 @CanIgnoreReturnValue 543 @Override 544 public Builder<E> addAll(Iterable<? extends E> elements) { 545 if (elements instanceof Multiset) { 546 Multiset<? extends E> multiset = Multisets.cast(elements); 547 multiset.forEachEntry((e, n) -> contents.add(checkNotNull(e), n)); 548 } else { 549 super.addAll(elements); 550 } 551 return this; 552 } 553 554 /** 555 * Adds each element of {@code elements} to the {@code ImmutableMultiset}. 556 * 557 * @param elements the elements to add to the {@code ImmutableMultiset} 558 * @return this {@code Builder} object 559 * @throws NullPointerException if {@code elements} is null or contains a null element 560 */ 561 @CanIgnoreReturnValue 562 @Override 563 public Builder<E> addAll(Iterator<? extends E> elements) { 564 super.addAll(elements); 565 return this; 566 } 567 568 /** 569 * Returns a newly-created {@code ImmutableMultiset} based on the contents of the {@code 570 * Builder}. 571 */ 572 @Override 573 public ImmutableMultiset<E> build() { 574 return copyOf(contents); 575 } 576 577 @VisibleForTesting 578 ImmutableMultiset<E> buildJdkBacked() { 579 if (contents.isEmpty()) { 580 return of(); 581 } 582 return JdkBackedImmutableMultiset.create(contents.entrySet()); 583 } 584 } 585 586 static final class ElementSet<E> extends ImmutableSet.Indexed<E> { 587 private final List<Entry<E>> entries; 588 // TODO(cpovirk): @Weak? 589 private final Multiset<E> delegate; 590 591 ElementSet(List<Entry<E>> entries, Multiset<E> delegate) { 592 this.entries = entries; 593 this.delegate = delegate; 594 } 595 596 @Override 597 E get(int index) { 598 return entries.get(index).getElement(); 599 } 600 601 @Override 602 public boolean contains(@CheckForNull Object object) { 603 return delegate.contains(object); 604 } 605 606 @Override 607 boolean isPartialView() { 608 return true; 609 } 610 611 @Override 612 public int size() { 613 return entries.size(); 614 } 615 } 616 617 static final class SerializedForm implements Serializable { 618 final Object[] elements; 619 final int[] counts; 620 621 // "extends Object" works around https://github.com/typetools/checker-framework/issues/3013 622 SerializedForm(Multiset<? extends Object> multiset) { 623 int distinct = multiset.entrySet().size(); 624 elements = new Object[distinct]; 625 counts = new int[distinct]; 626 int i = 0; 627 for (Entry<? extends Object> entry : multiset.entrySet()) { 628 elements[i] = entry.getElement(); 629 counts[i] = entry.getCount(); 630 i++; 631 } 632 } 633 634 Object readResolve() { 635 LinkedHashMultiset<Object> multiset = LinkedHashMultiset.create(elements.length); 636 for (int i = 0; i < elements.length; i++) { 637 multiset.add(elements[i], counts[i]); 638 } 639 return ImmutableMultiset.copyOf(multiset); 640 } 641 642 private static final long serialVersionUID = 0; 643 } 644}