1 /*
2 * Copyright (C) 2008 The Guava Authors
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 package com.google.common.collect;
18
19 import static com.google.common.base.Preconditions.checkNotNull;
20 import static java.util.Objects.requireNonNull;
21
22 import com.google.common.annotations.GwtCompatible;
23 import com.google.common.annotations.GwtIncompatible;
24 import com.google.common.annotations.VisibleForTesting;
25 import com.google.errorprone.annotations.CanIgnoreReturnValue;
26 import com.google.errorprone.annotations.DoNotCall;
27 import com.google.errorprone.annotations.concurrent.LazyInit;
28 import com.google.j2objc.annotations.WeakOuter;
29 import java.io.Serializable;
30 import java.util.Arrays;
31 import java.util.Collection;
32 import java.util.Collections;
33 import java.util.Iterator;
34 import java.util.List;
35 import java.util.function.Function;
36 import java.util.function.ToIntFunction;
37 import java.util.stream.Collector;
38 import javax.annotation.CheckForNull;
39 import org.checkerframework.checker.nullness.qual.Nullable;
40
41 /**
42 * A {@link Multiset} whose contents will never change, with many other important properties
43 * detailed at {@link ImmutableCollection}.
44 *
45 * <p><b>Grouped iteration.</b> In all current implementations, duplicate elements always appear
46 * consecutively when iterating. Elements iterate in order by the <i>first</i> appearance of that
47 * element when the multiset was created.
48 *
49 * <p>See the Guava User Guide article on <a href=
50 * "https://github.com/google/guava/wiki/ImmutableCollectionsExplained"> immutable collections</a>.
51 *
52 * @author Jared Levy
53 * @author Louis Wasserman
54 * @since 2.0
55 */
56 @GwtCompatible(serializable = true, emulated = true)
57 @SuppressWarnings("serial") // we're overriding default serialization
58 @ElementTypesAreNonnullByDefault
59 public abstract class ImmutableMultiset<E> extends ImmutableMultisetGwtSerializationDependencies<E>
60 implements Multiset<E> {
61
62 /**
63 * Returns a {@code Collector} that accumulates the input elements into a new {@code
64 * ImmutableMultiset}. Elements iterate in order by the <i>first</i> appearance of that element in
65 * encounter order.
66 *
67 * @since 21.0
68 */
69 public static <E> Collector<E, ?, ImmutableMultiset<E>> toImmutableMultiset() {
70 return CollectCollectors.toImmutableMultiset(Function.identity(), e -> 1);
71 }
72
73 /**
74 * Returns a {@code Collector} that accumulates elements into an {@code ImmutableMultiset} whose
75 * elements are the result of applying {@code elementFunction} to the inputs, with counts equal to
76 * the result of applying {@code countFunction} to the inputs.
77 *
78 * <p>If the mapped elements contain duplicates (according to {@link Object#equals}), the first
79 * occurrence in encounter order appears in the resulting multiset, with count equal to the sum of
80 * the outputs of {@code countFunction.applyAsInt(t)} for each {@code t} mapped to that element.
81 *
82 * @since 22.0
83 */
84 public static <T extends @Nullable Object, E>
85 Collector<T, ?, ImmutableMultiset<E>> toImmutableMultiset(
86 Function<? super T, ? extends E> elementFunction,
87 ToIntFunction<? super T> countFunction) {
88 return CollectCollectors.toImmutableMultiset(elementFunction, countFunction);
89 }
90
91 /**
92 * Returns the empty immutable multiset.
93 *
94 * <p><b>Performance note:</b> the instance returned is a singleton.
95 */
96 @SuppressWarnings("unchecked") // all supported methods are covariant
97 public static <E> ImmutableMultiset<E> of() {
98 return (ImmutableMultiset<E>) RegularImmutableMultiset.EMPTY;
99 }
100
101 /**
102 * Returns an immutable multiset containing a single element.
103 *
104 * @throws NullPointerException if {@code element} is null
105 * @since 6.0 (source-compatible since 2.0)
106 */
107 public static <E> ImmutableMultiset<E> of(E element) {
108 return copyFromElements(element);
109 }
110
111 /**
112 * Returns an immutable multiset containing the given elements, in order.
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) {
118 return copyFromElements(e1, e2);
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) {
129 return copyFromElements(e1, e2, e3);
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 element is null
137 * @since 6.0 (source-compatible since 2.0)
138 */
139 public static <E> ImmutableMultiset<E> of(E e1, E e2, E e3, E e4) {
140 return copyFromElements(e1, e2, e3, e4);
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 element is null
148 * @since 6.0 (source-compatible since 2.0)
149 */
150 public static <E> ImmutableMultiset<E> of(E e1, E e2, E e3, E e4, E e5) {
151 return copyFromElements(e1, e2, e3, e4, e5);
152 }
153
154 /**
155 * Returns an immutable multiset containing the given elements, in the "grouped iteration order"
156 * described in the class documentation.
157 *
158 * @throws NullPointerException if any element is null
159 * @since 6.0 (source-compatible since 2.0)
160 */
161 public static <E> ImmutableMultiset<E> of(E e1, E e2, E e3, E e4, E e5, E e6, E... others) {
162 return new Builder<E>().add(e1).add(e2).add(e3).add(e4).add(e5).add(e6).add(others).build();
163 }
164
165 /**
166 * Returns an immutable multiset containing the given elements, in the "grouped iteration order"
167 * described in the class documentation.
168 *
169 * @throws NullPointerException if any of {@code elements} is null
170 * @since 6.0
171 */
172 public static <E> ImmutableMultiset<E> copyOf(E[] elements) {
173 return copyFromElements(elements);
174 }
175
176 /**
177 * Returns an immutable multiset containing the given elements, in the "grouped iteration order"
178 * described in the class documentation.
179 *
180 * @throws NullPointerException if any of {@code elements} is null
181 */
182 public static <E> ImmutableMultiset<E> copyOf(Iterable<? extends E> elements) {
183 if (elements instanceof ImmutableMultiset) {
184 @SuppressWarnings("unchecked") // all supported methods are covariant
185 ImmutableMultiset<E> result = (ImmutableMultiset<E>) elements;
186 if (!result.isPartialView()) {
187 return result;
188 }
189 }
190
191 Multiset<? extends E> multiset =
192 (elements instanceof Multiset)
193 ? Multisets.cast(elements)
194 : LinkedHashMultiset.create(elements);
195
196 return copyFromEntries(multiset.entrySet());
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 Multiset<E> multiset = LinkedHashMultiset.create();
207 Iterators.addAll(multiset, elements);
208 return copyFromEntries(multiset.entrySet());
209 }
210
211 private static <E> ImmutableMultiset<E> copyFromElements(E... elements) {
212 Multiset<E> multiset = LinkedHashMultiset.create();
213 Collections.addAll(multiset, elements);
214 return copyFromEntries(multiset.entrySet());
215 }
216
217 static <E> ImmutableMultiset<E> copyFromEntries(
218 Collection<? extends Entry<? extends E>> entries) {
219 if (entries.isEmpty()) {
220 return of();
221 } else {
222 return RegularImmutableMultiset.create(entries);
223 }
224 }
225
226 ImmutableMultiset() {}
227
228 @Override
229 public UnmodifiableIterator<E> iterator() {
230 final Iterator<Entry<E>> entryIterator = entrySet().iterator();
231 return new UnmodifiableIterator<E>() {
232 int remaining;
233 @CheckForNull E element;
234
235 @Override
236 public boolean hasNext() {
237 return (remaining > 0) || entryIterator.hasNext();
238 }
239
240 @Override
241 public E next() {
242 if (remaining <= 0) {
243 Entry<E> entry = entryIterator.next();
244 element = entry.getElement();
245 remaining = entry.getCount();
246 }
247 remaining--;
248 /*
249 * requireNonNull is safe because `remaining` starts at 0, forcing us to initialize
250 * `element` above. After that, we never clear it.
251 */
252 return requireNonNull(element);
253 }
254 };
255 }
256
257 @LazyInit @CheckForNull private transient ImmutableList<E> asList;
258
259 @Override
260 public ImmutableList<E> asList() {
261 ImmutableList<E> result = asList;
262 return (result == null) ? asList = super.asList() : result;
263 }
264
265 @Override
266 public boolean contains(@CheckForNull Object object) {
267 return count(object) > 0;
268 }
269
270 /**
271 * Guaranteed to throw an exception and leave the collection unmodified.
272 *
273 * @throws UnsupportedOperationException always
274 * @deprecated Unsupported operation.
275 */
276 @CanIgnoreReturnValue
277 @Deprecated
278 @Override
279 @DoNotCall("Always throws UnsupportedOperationException")
280 public final int add(E element, int occurrences) {
281 throw new UnsupportedOperationException();
282 }
283
284 /**
285 * Guaranteed to throw an exception and leave the collection unmodified.
286 *
287 * @throws UnsupportedOperationException always
288 * @deprecated Unsupported operation.
289 */
290 @CanIgnoreReturnValue
291 @Deprecated
292 @Override
293 @DoNotCall("Always throws UnsupportedOperationException")
294 public final int remove(@CheckForNull Object element, int occurrences) {
295 throw new UnsupportedOperationException();
296 }
297
298 /**
299 * Guaranteed to throw an exception and leave the collection unmodified.
300 *
301 * @throws UnsupportedOperationException always
302 * @deprecated Unsupported operation.
303 */
304 @CanIgnoreReturnValue
305 @Deprecated
306 @Override
307 @DoNotCall("Always throws UnsupportedOperationException")
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 @DoNotCall("Always throws UnsupportedOperationException")
322 public final boolean setCount(E element, int oldCount, int newCount) {
323 throw new UnsupportedOperationException();
324 }
325
326 @GwtIncompatible // not present in emulated superclass
327 @Override
328 int copyIntoArray(Object[] dst, int offset) {
329 for (Multiset.Entry<E> entry : entrySet()) {
330 Arrays.fill(dst, offset, offset + entry.getCount(), entry.getElement());
331 offset += entry.getCount();
332 }
333 return offset;
334 }
335
336 @Override
337 public boolean equals(@CheckForNull Object object) {
338 return Multisets.equalsImpl(this, object);
339 }
340
341 @Override
342 public int hashCode() {
343 return Sets.hashCodeImpl(entrySet());
344 }
345
346 @Override
347 public String toString() {
348 return entrySet().toString();
349 }
350
351 /** @since 21.0 (present with return type {@code Set} since 2.0) */
352 @Override
353 public abstract ImmutableSet<E> elementSet();
354
355 @LazyInit @CheckForNull private transient ImmutableSet<Entry<E>> entrySet;
356
357 @Override
358 public ImmutableSet<Entry<E>> entrySet() {
359 ImmutableSet<Entry<E>> es = entrySet;
360 return (es == null) ? (entrySet = createEntrySet()) : es;
361 }
362
363 private ImmutableSet<Entry<E>> createEntrySet() {
364 return isEmpty() ? ImmutableSet.<Entry<E>>of() : new EntrySet();
365 }
366
367 abstract Entry<E> getEntry(int index);
368
369 @WeakOuter
370 private final class EntrySet extends IndexedImmutableSet<Entry<E>> {
371 @Override
372 boolean isPartialView() {
373 return ImmutableMultiset.this.isPartialView();
374 }
375
376 @Override
377 Entry<E> get(int index) {
378 return getEntry(index);
379 }
380
381 @Override
382 public int size() {
383 return elementSet().size();
384 }
385
386 @Override
387 public boolean contains(@CheckForNull Object o) {
388 if (o instanceof Entry) {
389 Entry<?> entry = (Entry<?>) o;
390 if (entry.getCount() <= 0) {
391 return false;
392 }
393 int count = count(entry.getElement());
394 return count == entry.getCount();
395 }
396 return false;
397 }
398
399 @Override
400 public int hashCode() {
401 return ImmutableMultiset.this.hashCode();
402 }
403
404 @GwtIncompatible
405 @Override
406 Object writeReplace() {
407 return new EntrySetSerializedForm<E>(ImmutableMultiset.this);
408 }
409
410 private static final long serialVersionUID = 0;
411 }
412
413 @GwtIncompatible
414 static class EntrySetSerializedForm<E> implements Serializable {
415 final ImmutableMultiset<E> multiset;
416
417 EntrySetSerializedForm(ImmutableMultiset<E> multiset) {
418 this.multiset = multiset;
419 }
420
421 Object readResolve() {
422 return multiset.entrySet();
423 }
424 }
425
426 @GwtIncompatible
427 @Override
428 Object writeReplace() {
429 return new SerializedForm(this);
430 }
431
432 /**
433 * Returns a new builder. The generated builder is equivalent to the builder created by the {@link
434 * Builder} constructor.
435 */
436 public static <E> Builder<E> builder() {
437 return new Builder<E>();
438 }
439
440 /**
441 * A builder for creating immutable multiset instances, especially {@code public static final}
442 * multisets ("constant multisets"). Example:
443 *
444 * <pre>{@code
445 * public static final ImmutableMultiset<Bean> BEANS =
446 * new ImmutableMultiset.Builder<Bean>()
447 * .addCopies(Bean.COCOA, 4)
448 * .addCopies(Bean.GARDEN, 6)
449 * .addCopies(Bean.RED, 8)
450 * .addCopies(Bean.BLACK_EYED, 10)
451 * .build();
452 * }</pre>
453 *
454 * <p>Builder instances can be reused; it is safe to call {@link #build} multiple times to build
455 * multiple multisets in series.
456 *
457 * @since 2.0
458 */
459 public static class Builder<E> extends ImmutableCollection.Builder<E> {
460 final Multiset<E> contents;
461
462 /**
463 * Creates a new builder. The returned builder is equivalent to the builder generated by {@link
464 * ImmutableMultiset#builder}.
465 */
466 public Builder() {
467 this(LinkedHashMultiset.<E>create());
468 }
469
470 Builder(Multiset<E> contents) {
471 this.contents = contents;
472 }
473
474 /**
475 * Adds {@code element} to the {@code ImmutableMultiset}.
476 *
477 * @param element the element to add
478 * @return this {@code Builder} object
479 * @throws NullPointerException if {@code element} is null
480 */
481 @CanIgnoreReturnValue
482 @Override
483 public Builder<E> add(E element) {
484 contents.add(checkNotNull(element));
485 return this;
486 }
487
488 /**
489 * Adds each element of {@code elements} to the {@code ImmutableMultiset}.
490 *
491 * @param elements the elements to add
492 * @return this {@code Builder} object
493 * @throws NullPointerException if {@code elements} is null or contains a null element
494 */
495 @CanIgnoreReturnValue
496 @Override
497 public Builder<E> add(E... elements) {
498 super.add(elements);
499 return this;
500 }
501
502 /**
503 * Adds a number of occurrences of an element to this {@code ImmutableMultiset}.
504 *
505 * @param element the element to add
506 * @param occurrences the number of occurrences of the element to add. May be zero, in which
507 * case no change will be made.
508 * @return this {@code Builder} object
509 * @throws NullPointerException if {@code element} is null
510 * @throws IllegalArgumentException if {@code occurrences} is negative, or if this operation
511 * would result in more than {@link Integer#MAX_VALUE} occurrences of the element
512 */
513 @CanIgnoreReturnValue
514 public Builder<E> addCopies(E element, int occurrences) {
515 contents.add(checkNotNull(element), occurrences);
516 return this;
517 }
518
519 /**
520 * Adds or removes the necessary occurrences of an element such that the element attains the
521 * desired count.
522 *
523 * @param element the element to add or remove occurrences of
524 * @param count the desired count of the element in this multiset
525 * @return this {@code Builder} object
526 * @throws NullPointerException if {@code element} is null
527 * @throws IllegalArgumentException if {@code count} is negative
528 */
529 @CanIgnoreReturnValue
530 public Builder<E> setCount(E element, int count) {
531 contents.setCount(checkNotNull(element), count);
532 return this;
533 }
534
535 /**
536 * Adds each element of {@code elements} to the {@code ImmutableMultiset}.
537 *
538 * @param elements the {@code Iterable} to add to the {@code ImmutableMultiset}
539 * @return this {@code Builder} object
540 * @throws NullPointerException if {@code elements} is null or contains a null element
541 */
542 @CanIgnoreReturnValue
543 @Override
544 public Builder<E> addAll(Iterable<? extends E> elements) {
545 if (elements instanceof Multiset) {
546 Multiset<? extends E> multiset = Multisets.cast(elements);
547 multiset.forEachEntry((e, n) -> contents.add(checkNotNull(e), n));
548 } else {
549 super.addAll(elements);
550 }
551 return this;
552 }
553
554 /**
555 * Adds each element of {@code elements} to the {@code ImmutableMultiset}.
556 *
557 * @param elements the elements to add to the {@code ImmutableMultiset}
558 * @return this {@code Builder} object
559 * @throws NullPointerException if {@code elements} is null or contains a null element
560 */
561 @CanIgnoreReturnValue
562 @Override
563 public Builder<E> addAll(Iterator<? extends E> elements) {
564 super.addAll(elements);
565 return this;
566 }
567
568 /**
569 * Returns a newly-created {@code ImmutableMultiset} based on the contents of the {@code
570 * Builder}.
571 */
572 @Override
573 public ImmutableMultiset<E> build() {
574 return copyOf(contents);
575 }
576
577 @VisibleForTesting
578 ImmutableMultiset<E> buildJdkBacked() {
579 if (contents.isEmpty()) {
580 return of();
581 }
582 return JdkBackedImmutableMultiset.create(contents.entrySet());
583 }
584 }
585
586 static final class ElementSet<E> extends ImmutableSet.Indexed<E> {
587 private final List<Entry<E>> entries;
588 // TODO(cpovirk): @Weak?
589 private final Multiset<E> delegate;
590
591 ElementSet(List<Entry<E>> entries, Multiset<E> delegate) {
592 this.entries = entries;
593 this.delegate = delegate;
594 }
595
596 @Override
597 E get(int index) {
598 return entries.get(index).getElement();
599 }
600
601 @Override
602 public boolean contains(@CheckForNull Object object) {
603 return delegate.contains(object);
604 }
605
606 @Override
607 boolean isPartialView() {
608 return true;
609 }
610
611 @Override
612 public int size() {
613 return entries.size();
614 }
615 }
616
617 static final class SerializedForm implements Serializable {
618 final Object[] elements;
619 final int[] counts;
620
621 // "extends Object" works around https://github.com/typetools/checker-framework/issues/3013
622 SerializedForm(Multiset<? extends Object> multiset) {
623 int distinct = multiset.entrySet().size();
624 elements = new Object[distinct];
625 counts = new int[distinct];
626 int i = 0;
627 for (Entry<? extends Object> entry : multiset.entrySet()) {
628 elements[i] = entry.getElement();
629 counts[i] = entry.getCount();
630 i++;
631 }
632 }
633
634 Object readResolve() {
635 LinkedHashMultiset<Object> multiset = LinkedHashMultiset.create(elements.length);
636 for (int i = 0; i < elements.length; i++) {
637 multiset.add(elements[i], counts[i]);
638 }
639 return ImmutableMultiset.copyOf(multiset);
640 }
641
642 private static final long serialVersionUID = 0;
643 }
644 }