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