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