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.J2ktIncompatible; 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.InvalidObjectException; 030import java.io.ObjectInputStream; 031import java.io.Serializable; 032import java.util.Arrays; 033import java.util.Collection; 034import java.util.Iterator; 035import java.util.Set; 036import java.util.function.Function; 037import java.util.function.ToIntFunction; 038import java.util.stream.Collector; 039import org.jspecify.annotations.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 058public abstract class ImmutableMultiset<E> extends ImmutableMultisetGwtSerializationDependencies<E> 059 implements Multiset<E> { 060 061 /** 062 * Returns a {@code Collector} that accumulates the input elements into a new {@code 063 * ImmutableMultiset}. Elements iterate in order by the <i>first</i> appearance of that element in 064 * encounter order. 065 * 066 * @since 33.2.0 (available since 21.0 in guava-jre) 067 */ 068 @SuppressWarnings("Java7ApiChecker") 069 @IgnoreJRERequirement // Users will use this only if they're already using streams. 070 public static <E> Collector<E, ?, ImmutableMultiset<E>> toImmutableMultiset() { 071 return CollectCollectors.toImmutableMultiset(Function.identity(), e -> 1); 072 } 073 074 /** 075 * Returns a {@code Collector} that accumulates elements into an {@code ImmutableMultiset} whose 076 * elements are the result of applying {@code elementFunction} to the inputs, with counts equal to 077 * the result of applying {@code countFunction} to the inputs. 078 * 079 * <p>If the mapped elements contain duplicates (according to {@link Object#equals}), the first 080 * occurrence in encounter order appears in the resulting multiset, with count equal to the sum of 081 * the outputs of {@code countFunction.applyAsInt(t)} for each {@code t} mapped to that element. 082 * 083 * @since 33.2.0 (available since 22.0 in guava-jre) 084 */ 085 @SuppressWarnings("Java7ApiChecker") 086 @IgnoreJRERequirement // Users will use this only if they're already using streams. 087 public static <T extends @Nullable Object, E> 088 Collector<T, ?, ImmutableMultiset<E>> toImmutableMultiset( 089 Function<? super T, ? extends E> elementFunction, 090 ToIntFunction<? super T> countFunction) { 091 return CollectCollectors.toImmutableMultiset(elementFunction, countFunction); 092 } 093 094 /** 095 * Returns the empty immutable multiset. 096 * 097 * <p><b>Performance note:</b> the instance returned is a singleton. 098 */ 099 @SuppressWarnings("unchecked") // all supported methods are covariant 100 public static <E> ImmutableMultiset<E> of() { 101 return (ImmutableMultiset<E>) RegularImmutableMultiset.EMPTY; 102 } 103 104 /** 105 * Returns an immutable multiset containing a single element. 106 * 107 * @throws NullPointerException if the element is null 108 * @since 6.0 (source-compatible since 2.0) 109 */ 110 public static <E> ImmutableMultiset<E> of(E e1) { 111 return copyFromElements(e1); 112 } 113 114 /** 115 * Returns an immutable multiset containing the given elements, in order. 116 * 117 * @throws NullPointerException if any element is null 118 * @since 6.0 (source-compatible since 2.0) 119 */ 120 public static <E> ImmutableMultiset<E> of(E e1, E e2) { 121 return copyFromElements(e1, e2); 122 } 123 124 /** 125 * Returns an immutable multiset containing the given elements, in the "grouped iteration order" 126 * described in the class documentation. 127 * 128 * @throws NullPointerException if any element is null 129 * @since 6.0 (source-compatible since 2.0) 130 */ 131 public static <E> ImmutableMultiset<E> of(E e1, E e2, E e3) { 132 return copyFromElements(e1, e2, e3); 133 } 134 135 /** 136 * Returns an immutable multiset containing the given elements, in the "grouped iteration order" 137 * described in the class documentation. 138 * 139 * @throws NullPointerException if any element is null 140 * @since 6.0 (source-compatible since 2.0) 141 */ 142 public static <E> ImmutableMultiset<E> of(E e1, E e2, E e3, E e4) { 143 return copyFromElements(e1, e2, e3, e4); 144 } 145 146 /** 147 * Returns an immutable multiset containing the given elements, in the "grouped iteration order" 148 * described in the class documentation. 149 * 150 * @throws NullPointerException if any element is null 151 * @since 6.0 (source-compatible since 2.0) 152 */ 153 public static <E> ImmutableMultiset<E> of(E e1, E e2, E e3, E e4, E e5) { 154 return copyFromElements(e1, e2, e3, e4, e5); 155 } 156 157 /** 158 * Returns an immutable multiset containing the given elements, in the "grouped iteration order" 159 * described in the class documentation. 160 * 161 * @throws NullPointerException if any element is null 162 * @since 6.0 (source-compatible since 2.0) 163 */ 164 public static <E> ImmutableMultiset<E> of(E e1, E e2, E e3, E e4, E e5, E e6, E... others) { 165 return new Builder<E>().add(e1).add(e2).add(e3).add(e4).add(e5).add(e6).add(others).build(); 166 } 167 168 /** 169 * Returns an immutable multiset containing the given elements, in the "grouped iteration order" 170 * described in the class documentation. 171 * 172 * @throws NullPointerException if any of {@code elements} is null 173 * @since 6.0 174 */ 175 public static <E> ImmutableMultiset<E> copyOf(E[] elements) { 176 return copyFromElements(elements); 177 } 178 179 /** 180 * Returns an immutable multiset containing the given elements, in the "grouped iteration order" 181 * described in the class documentation. 182 * 183 * @throws NullPointerException if any of {@code elements} is null 184 */ 185 public static <E> ImmutableMultiset<E> copyOf(Iterable<? extends E> elements) { 186 if (elements instanceof ImmutableMultiset) { 187 @SuppressWarnings("unchecked") // all supported methods are covariant 188 ImmutableMultiset<E> result = (ImmutableMultiset<E>) elements; 189 if (!result.isPartialView()) { 190 return result; 191 } 192 } 193 ImmutableMultiset.Builder<E> builder = 194 new ImmutableMultiset.Builder<E>(Multisets.inferDistinctElements(elements)); 195 builder.addAll(elements); 196 return builder.build(); 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 return new ImmutableMultiset.Builder<E>().addAll(elements).build(); 207 } 208 209 private static <E> ImmutableMultiset<E> copyFromElements(E... elements) { 210 return new ImmutableMultiset.Builder<E>().add(elements).build(); 211 } 212 213 static <E> ImmutableMultiset<E> copyFromEntries( 214 Collection<? extends Entry<? extends E>> entries) { 215 ImmutableMultiset.Builder<E> builder = new ImmutableMultiset.Builder<E>(entries.size()); 216 for (Entry<? extends E> entry : entries) { 217 builder.addCopies(entry.getElement(), entry.getCount()); 218 } 219 return builder.build(); 220 } 221 222 ImmutableMultiset() {} 223 224 @Override 225 public UnmodifiableIterator<E> iterator() { 226 final Iterator<Entry<E>> entryIterator = entrySet().iterator(); 227 return new UnmodifiableIterator<E>() { 228 int remaining; 229 @Nullable E element; 230 231 @Override 232 public boolean hasNext() { 233 return (remaining > 0) || entryIterator.hasNext(); 234 } 235 236 @Override 237 public E next() { 238 if (remaining <= 0) { 239 Entry<E> entry = entryIterator.next(); 240 element = entry.getElement(); 241 remaining = entry.getCount(); 242 } 243 remaining--; 244 /* 245 * requireNonNull is safe because `remaining` starts at 0, forcing us to initialize 246 * `element` above. After that, we never clear it. 247 */ 248 return requireNonNull(element); 249 } 250 }; 251 } 252 253 @LazyInit private transient @Nullable ImmutableList<E> asList; 254 255 @Override 256 public ImmutableList<E> asList() { 257 ImmutableList<E> result = asList; 258 return (result == null) ? asList = super.asList() : result; 259 } 260 261 @Override 262 public boolean contains(@Nullable Object object) { 263 return count(object) > 0; 264 } 265 266 /** 267 * Guaranteed to throw an exception and leave the collection unmodified. 268 * 269 * @throws UnsupportedOperationException always 270 * @deprecated Unsupported operation. 271 */ 272 @CanIgnoreReturnValue 273 @Deprecated 274 @Override 275 @DoNotCall("Always throws UnsupportedOperationException") 276 public final int add(E element, int occurrences) { 277 throw new UnsupportedOperationException(); 278 } 279 280 /** 281 * Guaranteed to throw an exception and leave the collection unmodified. 282 * 283 * @throws UnsupportedOperationException always 284 * @deprecated Unsupported operation. 285 */ 286 @CanIgnoreReturnValue 287 @Deprecated 288 @Override 289 @DoNotCall("Always throws UnsupportedOperationException") 290 public final int remove(@Nullable Object element, int occurrences) { 291 throw new UnsupportedOperationException(); 292 } 293 294 /** 295 * Guaranteed to throw an exception and leave the collection unmodified. 296 * 297 * @throws UnsupportedOperationException always 298 * @deprecated Unsupported operation. 299 */ 300 @CanIgnoreReturnValue 301 @Deprecated 302 @Override 303 @DoNotCall("Always throws UnsupportedOperationException") 304 public final int setCount(E element, int count) { 305 throw new UnsupportedOperationException(); 306 } 307 308 /** 309 * Guaranteed to throw an exception and leave the collection unmodified. 310 * 311 * @throws UnsupportedOperationException always 312 * @deprecated Unsupported operation. 313 */ 314 @CanIgnoreReturnValue 315 @Deprecated 316 @Override 317 @DoNotCall("Always throws UnsupportedOperationException") 318 public final boolean setCount(E element, int oldCount, int newCount) { 319 throw new UnsupportedOperationException(); 320 } 321 322 @GwtIncompatible // not present in emulated superclass 323 @Override 324 int copyIntoArray(@Nullable Object[] dst, int offset) { 325 for (Multiset.Entry<E> entry : entrySet()) { 326 Arrays.fill(dst, offset, offset + entry.getCount(), entry.getElement()); 327 offset += entry.getCount(); 328 } 329 return offset; 330 } 331 332 @Override 333 public boolean equals(@Nullable Object object) { 334 return Multisets.equalsImpl(this, object); 335 } 336 337 @Override 338 public int hashCode() { 339 return Sets.hashCodeImpl(entrySet()); 340 } 341 342 @Override 343 public String toString() { 344 return entrySet().toString(); 345 } 346 347 /** @since 21.0 (present with return type {@code Set} since 2.0) */ 348 @Override 349 public abstract ImmutableSet<E> elementSet(); 350 351 @LazyInit private transient @Nullable ImmutableSet<Entry<E>> entrySet; 352 353 @Override 354 public ImmutableSet<Entry<E>> entrySet() { 355 ImmutableSet<Entry<E>> es = entrySet; 356 return (es == null) ? (entrySet = createEntrySet()) : es; 357 } 358 359 private ImmutableSet<Entry<E>> createEntrySet() { 360 return isEmpty() ? ImmutableSet.<Entry<E>>of() : new EntrySet(); 361 } 362 363 abstract Entry<E> getEntry(int index); 364 365 @WeakOuter 366 private final class EntrySet extends IndexedImmutableSet<Entry<E>> { 367 @Override 368 boolean isPartialView() { 369 return ImmutableMultiset.this.isPartialView(); 370 } 371 372 @Override 373 Entry<E> get(int index) { 374 return getEntry(index); 375 } 376 377 @Override 378 public int size() { 379 return elementSet().size(); 380 } 381 382 @Override 383 public boolean contains(@Nullable Object o) { 384 if (o instanceof Entry) { 385 Entry<?> entry = (Entry<?>) o; 386 if (entry.getCount() <= 0) { 387 return false; 388 } 389 int count = count(entry.getElement()); 390 return count == entry.getCount(); 391 } 392 return false; 393 } 394 395 @Override 396 public int hashCode() { 397 return ImmutableMultiset.this.hashCode(); 398 } 399 400 @GwtIncompatible 401 @J2ktIncompatible 402 @Override 403 Object writeReplace() { 404 return new EntrySetSerializedForm<E>(ImmutableMultiset.this); 405 } 406 407 @GwtIncompatible 408 @J2ktIncompatible 409 private void readObject(ObjectInputStream stream) throws InvalidObjectException { 410 throw new InvalidObjectException("Use EntrySetSerializedForm"); 411 } 412 413 @J2ktIncompatible private static final long serialVersionUID = 0; 414 } 415 416 @GwtIncompatible 417 @J2ktIncompatible 418 static class EntrySetSerializedForm<E> implements Serializable { 419 final ImmutableMultiset<E> multiset; 420 421 EntrySetSerializedForm(ImmutableMultiset<E> multiset) { 422 this.multiset = multiset; 423 } 424 425 Object readResolve() { 426 return multiset.entrySet(); 427 } 428 } 429 430 @GwtIncompatible 431 @J2ktIncompatible 432 @Override 433 abstract Object writeReplace(); 434 435 @GwtIncompatible 436 @J2ktIncompatible 437 private void readObject(ObjectInputStream stream) throws InvalidObjectException { 438 throw new InvalidObjectException("Use SerializedForm"); 439 } 440 441 /** 442 * Returns a new builder. The generated builder is equivalent to the builder created by the {@link 443 * Builder} constructor. 444 */ 445 public static <E> Builder<E> builder() { 446 return new Builder<>(); 447 } 448 449 /** 450 * A builder for creating immutable multiset instances, especially {@code public static final} 451 * multisets ("constant multisets"). Example: 452 * 453 * <pre>{@code 454 * public static final ImmutableMultiset<Bean> BEANS = 455 * new ImmutableMultiset.Builder<Bean>() 456 * .addCopies(Bean.COCOA, 4) 457 * .addCopies(Bean.GARDEN, 6) 458 * .addCopies(Bean.RED, 8) 459 * .addCopies(Bean.BLACK_EYED, 10) 460 * .build(); 461 * }</pre> 462 * 463 * <p>Builder instances can be reused; it is safe to call {@link #build} multiple times to build 464 * multiple multisets in series. 465 * 466 * @since 2.0 467 */ 468 public static class Builder<E> extends ImmutableCollection.Builder<E> { 469 /* 470 * `contents` is null only for instances of the subclass, ImmutableSortedMultiset.Builder. That 471 * subclass overrides all the methods that access it here. Thus, all the methods here can safely 472 * assume that this field is non-null. 473 */ 474 @Nullable ObjectCountHashMap<E> contents; 475 476 /** 477 * If build() has been called on the current contents multiset, we need to copy it on any future 478 * modifications, or we'll modify the already-built ImmutableMultiset. 479 */ 480 boolean buildInvoked = false; 481 /** 482 * In the event of a setCount(elem, 0) call, we may need to remove elements, which destroys the 483 * insertion order property of ObjectCountHashMap. In that event, we need to convert to a 484 * ObjectCountLinkedHashMap, but we need to know we did that so we can convert back. 485 */ 486 boolean isLinkedHash = false; 487 488 /** 489 * Creates a new builder. The returned builder is equivalent to the builder generated by {@link 490 * ImmutableMultiset#builder}. 491 */ 492 public Builder() { 493 this(4); 494 } 495 496 Builder(int estimatedDistinct) { 497 this.contents = ObjectCountHashMap.createWithExpectedSize(estimatedDistinct); 498 } 499 500 Builder(boolean forSubtype) { 501 // for ImmutableSortedMultiset not to allocate data structures not used there 502 this.contents = null; 503 } 504 505 /** 506 * Adds {@code element} to the {@code ImmutableMultiset}. 507 * 508 * @param element the element to add 509 * @return this {@code Builder} object 510 * @throws NullPointerException if {@code element} is null 511 */ 512 @CanIgnoreReturnValue 513 @Override 514 public Builder<E> add(E element) { 515 return addCopies(element, 1); 516 } 517 518 /** 519 * Adds each element of {@code elements} to the {@code ImmutableMultiset}. 520 * 521 * @param elements the elements to add 522 * @return this {@code Builder} object 523 * @throws NullPointerException if {@code elements} is null or contains a null element 524 */ 525 @CanIgnoreReturnValue 526 @Override 527 public Builder<E> add(E... elements) { 528 super.add(elements); 529 return this; 530 } 531 532 /** 533 * Adds a number of occurrences of an element to this {@code ImmutableMultiset}. 534 * 535 * @param element the element to add 536 * @param occurrences the number of occurrences of the element to add. May be zero, in which 537 * case no change will be made. 538 * @return this {@code Builder} object 539 * @throws NullPointerException if {@code element} is null 540 * @throws IllegalArgumentException if {@code occurrences} is negative, or if this operation 541 * would result in more than {@link Integer#MAX_VALUE} occurrences of the element 542 */ 543 @CanIgnoreReturnValue 544 public Builder<E> addCopies(E element, int occurrences) { 545 requireNonNull(contents); // see the comment on the field 546 if (occurrences == 0) { 547 return this; 548 } 549 if (buildInvoked) { 550 contents = new ObjectCountHashMap<E>(contents); 551 isLinkedHash = false; 552 } 553 buildInvoked = false; 554 checkNotNull(element); 555 contents.put(element, occurrences + contents.get(element)); 556 return this; 557 } 558 559 /** 560 * Adds or removes the necessary occurrences of an element such that the element attains the 561 * desired count. 562 * 563 * @param element the element to add or remove occurrences of 564 * @param count the desired count of the element in this multiset 565 * @return this {@code Builder} object 566 * @throws NullPointerException if {@code element} is null 567 * @throws IllegalArgumentException if {@code count} is negative 568 */ 569 @CanIgnoreReturnValue 570 public Builder<E> setCount(E element, int count) { 571 requireNonNull(contents); // see the comment on the field 572 if (count == 0 && !isLinkedHash) { 573 contents = new ObjectCountLinkedHashMap<E>(contents); 574 isLinkedHash = true; 575 // to preserve insertion order through deletions, we have to switch to an actual linked 576 // implementation at least for now, but this should be a super rare case 577 } else if (buildInvoked) { 578 contents = new ObjectCountHashMap<E>(contents); 579 isLinkedHash = false; 580 } 581 buildInvoked = false; 582 checkNotNull(element); 583 if (count == 0) { 584 contents.remove(element); 585 } else { 586 contents.put(checkNotNull(element), count); 587 } 588 return this; 589 } 590 591 /** 592 * Adds each element of {@code elements} to the {@code ImmutableMultiset}. 593 * 594 * @param elements the {@code Iterable} to add to the {@code ImmutableMultiset} 595 * @return this {@code Builder} object 596 * @throws NullPointerException if {@code elements} is null or contains a null element 597 */ 598 @CanIgnoreReturnValue 599 @Override 600 public Builder<E> addAll(Iterable<? extends E> elements) { 601 requireNonNull(contents); // see the comment on the field 602 if (elements instanceof Multiset) { 603 Multiset<? extends E> multiset = (Multiset<? extends E>) elements; 604 ObjectCountHashMap<? extends E> backingMap = tryGetMap(multiset); 605 if (backingMap != null) { 606 contents.ensureCapacity(Math.max(contents.size(), backingMap.size())); 607 for (int i = backingMap.firstIndex(); i >= 0; i = backingMap.nextIndex(i)) { 608 addCopies(backingMap.getKey(i), backingMap.getValue(i)); 609 } 610 } else { 611 Set<? extends Entry<? extends E>> entries = multiset.entrySet(); 612 contents.ensureCapacity(Math.max(contents.size(), entries.size())); // might overlap 613 for (Entry<? extends E> entry : multiset.entrySet()) { 614 addCopies(entry.getElement(), entry.getCount()); 615 } 616 } 617 } else { 618 super.addAll(elements); 619 } 620 return this; 621 } 622 623 /** 624 * Adds each element of {@code elements} to the {@code ImmutableMultiset}. 625 * 626 * @param elements the elements to add to the {@code ImmutableMultiset} 627 * @return this {@code Builder} object 628 * @throws NullPointerException if {@code elements} is null or contains a null element 629 */ 630 @CanIgnoreReturnValue 631 @Override 632 public Builder<E> addAll(Iterator<? extends E> elements) { 633 super.addAll(elements); 634 return this; 635 } 636 637 /** 638 * If the specified collection is backed by an ObjectCountHashMap, it will be much more 639 * efficient to iterate over it by index rather than an entry iterator, which will need to 640 * allocate an object for each entry, so we check for that. 641 */ 642 static <T> @Nullable ObjectCountHashMap<T> tryGetMap(Iterable<T> multiset) { 643 if (multiset instanceof RegularImmutableMultiset) { 644 return ((RegularImmutableMultiset<T>) multiset).contents; 645 } else if (multiset instanceof AbstractMapBasedMultiset) { 646 return ((AbstractMapBasedMultiset<T>) multiset).backingMap; 647 } else { 648 return null; 649 } 650 } 651 652 /** 653 * Returns a newly-created {@code ImmutableMultiset} based on the contents of the {@code 654 * Builder}. 655 */ 656 @Override 657 public ImmutableMultiset<E> build() { 658 requireNonNull(contents); // see the comment on the field 659 if (contents.size() == 0) { 660 return of(); 661 } 662 if (isLinkedHash) { 663 // we need ObjectCountHashMap-backed contents, with its keys and values array in direct 664 // insertion order 665 contents = new ObjectCountHashMap<E>(contents); 666 isLinkedHash = false; 667 } 668 buildInvoked = true; 669 // contents is now ObjectCountHashMap, but still guaranteed to be in insertion order! 670 return new RegularImmutableMultiset<E>(contents); 671 } 672 } 673 674 private static final long serialVersionUID = 0xdecaf; 675}