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