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