Source code

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 com.google.common.collect.Sets.hashCodeImpl;
021import static java.util.Objects.requireNonNull;
022
023import com.google.common.annotations.GwtCompatible;
024import com.google.common.annotations.GwtIncompatible;
025import com.google.common.annotations.J2ktIncompatible;
026import com.google.common.annotations.VisibleForTesting;
027import com.google.errorprone.annotations.CanIgnoreReturnValue;
028import com.google.errorprone.annotations.DoNotCall;
029import com.google.errorprone.annotations.concurrent.LazyInit;
030import com.google.j2objc.annotations.WeakOuter;
031import java.io.InvalidObjectException;
032import java.io.ObjectInputStream;
033import java.io.Serializable;
034import java.util.Arrays;
035import java.util.Collection;
036import java.util.Collections;
037import java.util.Iterator;
038import java.util.List;
039import java.util.function.Function;
040import java.util.function.ToIntFunction;
041import java.util.stream.Collector;
042import org.jspecify.annotations.Nullable;
043
044/**
045 * A {@link Multiset} whose contents will never change, with many other important properties
046 * detailed at {@link ImmutableCollection}.
047 *
048 * <p><b>Grouped iteration.</b> In all current implementations, duplicate elements always appear
049 * consecutively when iterating. Elements iterate in order by the <i>first</i> appearance of that
050 * element when the multiset was created.
051 *
052 * <p>See the Guava User Guide article on <a href=
053 * "https://github.com/google/guava/wiki/ImmutableCollectionsExplained">immutable collections</a>.
054 *
055 * @author Jared Levy
056 * @author Louis Wasserman
057 * @since 2.0
058 */
059@GwtCompatible
060@SuppressWarnings("serial") // we're overriding default serialization
061public abstract class ImmutableMultiset<E> extends ImmutableCollection<E> implements Multiset<E> {
062
063  /**
064   * Returns a {@code Collector} that accumulates the input elements into a new {@code
065   * ImmutableMultiset}. Elements iterate in order by the <i>first</i> appearance of that element in
066   * encounter order.
067   *
068   * @since 21.0
069   */
070  public static <E> Collector<E, ?, ImmutableMultiset<E>> toImmutableMultiset() {
071    return CollectCollectors.toImmutableMultiset(Function.identity(), e -> 1);
072  }
073
074  /**
075   * Returns a {@code Collector} that accumulates elements into an {@code ImmutableMultiset} whose
076   * elements are the result of applying {@code elementFunction} to the inputs, with counts equal to
077   * the result of applying {@code countFunction} to the inputs.
078   *
079   * <p>If the mapped elements contain duplicates (according to {@link Object#equals}), the first
080   * occurrence in encounter order appears in the resulting multiset, with count equal to the sum of
081   * the outputs of {@code countFunction.applyAsInt(t)} for each {@code t} mapped to that element.
082   *
083   * @since 22.0
084   */
085  public static <T extends @Nullable Object, E>
086      Collector<T, ?, ImmutableMultiset<E>> toImmutableMultiset(
087          Function<? super T, ? extends E> elementFunction,
088          ToIntFunction<? super T> countFunction) {
089    return CollectCollectors.toImmutableMultiset(elementFunction, countFunction);
090  }
091
092  /**
093   * Returns the empty immutable multiset.
094   *
095   * <p><b>Performance note:</b> the instance returned is a singleton.
096   */
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 the element is null
106   * @since 6.0 (source-compatible since 2.0)
107   */
108  public static <E> ImmutableMultiset<E> of(E e1) {
109    return copyFromElements(e1);
110  }
111
112  /**
113   * Returns an immutable multiset containing the given elements, in order.
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) {
119    return copyFromElements(e1, e2);
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) {
130    return copyFromElements(e1, e2, e3);
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 element is null
138   * @since 6.0 (source-compatible since 2.0)
139   */
140  public static <E> ImmutableMultiset<E> of(E e1, E e2, E e3, E e4) {
141    return copyFromElements(e1, e2, e3, e4);
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 element is null
149   * @since 6.0 (source-compatible since 2.0)
150   */
151  public static <E> ImmutableMultiset<E> of(E e1, E e2, E e3, E e4, E e5) {
152    return copyFromElements(e1, e2, e3, e4, e5);
153  }
154
155  /**
156   * Returns an immutable multiset containing the given elements, in the "grouped iteration order"
157   * described in the class documentation.
158   *
159   * @throws NullPointerException if any element is null
160   * @since 6.0 (source-compatible since 2.0)
161   */
162  public static <E> ImmutableMultiset<E> of(E e1, E e2, E e3, E e4, E e5, E e6, E... others) {
163    return new Builder<E>().add(e1).add(e2).add(e3).add(e4).add(e5).add(e6).add(others).build();
164  }
165
166  /**
167   * Returns an immutable multiset containing the given elements, in the "grouped iteration order"
168   * described in the class documentation.
169   *
170   * @throws NullPointerException if any of {@code elements} is null
171   * @since 6.0
172   */
173  public static <E> ImmutableMultiset<E> copyOf(E[] elements) {
174    return copyFromElements(elements);
175  }
176
177  /**
178   * Returns an immutable multiset containing the given elements, in the "grouped iteration order"
179   * described in the class documentation.
180   *
181   * @throws NullPointerException if any of {@code elements} is null
182   */
183  public static <E> ImmutableMultiset<E> copyOf(Iterable<? extends E> elements) {
184    if (elements instanceof ImmutableMultiset) {
185      @SuppressWarnings("unchecked") // all supported methods are covariant
186      ImmutableMultiset<E> result = (ImmutableMultiset<E>) elements;
187      if (!result.isPartialView()) {
188        return result;
189      }
190    }
191
192    Multiset<? extends E> multiset =
193        (elements instanceof Multiset)
194            ? (Multiset<? extends E>) elements
195            : LinkedHashMultiset.create(elements);
196
197    return copyFromEntries(multiset.entrySet());
198  }
199
200  /**
201   * Returns an immutable multiset containing the given elements, in the "grouped iteration order"
202   * described in the class documentation.
203   *
204   * @throws NullPointerException if any of {@code elements} is null
205   */
206  public static <E> ImmutableMultiset<E> copyOf(Iterator<? extends E> elements) {
207    Multiset<E> multiset = LinkedHashMultiset.create();
208    Iterators.addAll(multiset, elements);
209    return copyFromEntries(multiset.entrySet());
210  }
211
212  private static <E> ImmutableMultiset<E> copyFromElements(E... elements) {
213    Multiset<E> multiset = LinkedHashMultiset.create();
214    Collections.addAll(multiset, elements);
215    return copyFromEntries(multiset.entrySet());
216  }
217
218  static <E> ImmutableMultiset<E> copyFromEntries(
219      Collection<? extends Entry<? extends E>> entries) {
220    if (entries.isEmpty()) {
221      return of();
222    } else {
223      return RegularImmutableMultiset.create(entries);
224    }
225  }
226
227  ImmutableMultiset() {}
228
229  @Override
230  public UnmodifiableIterator<E> iterator() {
231    Iterator<Entry<E>> entryIterator = entrySet().iterator();
232    return new UnmodifiableIterator<E>() {
233      int remaining;
234      @Nullable E element;
235
236      @Override
237      public boolean hasNext() {
238        return (remaining > 0) || entryIterator.hasNext();
239      }
240
241      @Override
242      public E next() {
243        if (remaining <= 0) {
244          Entry<E> entry = entryIterator.next();
245          element = entry.getElement();
246          remaining = entry.getCount();
247        }
248        remaining--;
249        /*
250         * requireNonNull is safe because `remaining` starts at 0, forcing us to initialize
251         * `element` above. After that, we never clear it.
252         */
253        return requireNonNull(element);
254      }
255    };
256  }
257
258  @LazyInit private transient @Nullable ImmutableList<E> asList;
259
260  @Override
261  public final ImmutableList<E> asList() {
262    ImmutableList<E> result = asList;
263    if (result == null) {
264      result = asList = super.asList();
265    }
266    return result;
267  }
268
269  @Override
270  public boolean contains(@Nullable Object object) {
271    return count(object) > 0;
272  }
273
274  /**
275   * Guaranteed to throw an exception and leave the collection unmodified.
276   *
277   * @throws UnsupportedOperationException always
278   * @deprecated Unsupported operation.
279   */
280  @CanIgnoreReturnValue
281  @Deprecated
282  @Override
283  @DoNotCall("Always throws UnsupportedOperationException")
284  public final int add(E element, int occurrences) {
285    throw new UnsupportedOperationException();
286  }
287
288  /**
289   * Guaranteed to throw an exception and leave the collection unmodified.
290   *
291   * @throws UnsupportedOperationException always
292   * @deprecated Unsupported operation.
293   */
294  @CanIgnoreReturnValue
295  @Deprecated
296  @Override
297  @DoNotCall("Always throws UnsupportedOperationException")
298  public final int remove(@Nullable 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  @DoNotCall("Always throws UnsupportedOperationException")
312  public final int setCount(E element, int count) {
313    throw new UnsupportedOperationException();
314  }
315
316  /**
317   * Guaranteed to throw an exception and leave the collection unmodified.
318   *
319   * @throws UnsupportedOperationException always
320   * @deprecated Unsupported operation.
321   */
322  @CanIgnoreReturnValue
323  @Deprecated
324  @Override
325  @DoNotCall("Always throws UnsupportedOperationException")
326  public final boolean setCount(E element, int oldCount, int newCount) {
327    throw new UnsupportedOperationException();
328  }
329
330  @GwtIncompatible // not present in emulated superclass
331  @Override
332  final int copyIntoArray(@Nullable Object[] dst, int offset) {
333    for (Entry<E> entry : entrySet()) {
334      Arrays.fill(dst, offset, offset + entry.getCount(), entry.getElement());
335      offset += entry.getCount();
336    }
337    return offset;
338  }
339
340  @Override
341  public final boolean equals(@Nullable Object object) {
342    return Multisets.equalsImpl(this, object);
343  }
344
345  @Override
346  public int hashCode() {
347    return hashCodeImpl(entrySet());
348  }
349
350  @Override
351  public final String toString() {
352    return entrySet().toString();
353  }
354
355  /**
356   * @since 21.0 (present with return type {@code Set} since 2.0)
357   */
358  @Override
359  public abstract ImmutableSet<E> elementSet();
360
361  @LazyInit private transient @Nullable ImmutableSet<Entry<E>> entrySet;
362
363  @Override
364  public final ImmutableSet<Entry<E>> entrySet() {
365    ImmutableSet<Entry<E>> result = entrySet;
366    if (result == null) {
367      result = entrySet = createEntrySet();
368    }
369    return result;
370  }
371
372  private ImmutableSet<Entry<E>> createEntrySet() {
373    return isEmpty() ? ImmutableSet.of() : new EntrySet();
374  }
375
376  abstract Entry<E> getEntry(int index);
377
378  @WeakOuter
379  private final class EntrySet extends IndexedImmutableSet<Entry<E>> {
380    @Override
381    boolean isPartialView() {
382      return ImmutableMultiset.this.isPartialView();
383    }
384
385    @Override
386    Entry<E> get(int index) {
387      return getEntry(index);
388    }
389
390    @Override
391    public int size() {
392      return elementSet().size();
393    }
394
395    @Override
396    public boolean contains(@Nullable Object o) {
397      if (o instanceof Entry) {
398        Entry<?> entry = (Entry<?>) o;
399        if (entry.getCount() <= 0) {
400          return false;
401        }
402        int count = count(entry.getElement());
403        return count == entry.getCount();
404      }
405      return false;
406    }
407
408    @Override
409    public int hashCode() {
410      return ImmutableMultiset.this.hashCode();
411    }
412
413    @GwtIncompatible
414    @J2ktIncompatible
415    @Override
416        Object writeReplace() {
417      return new EntrySetSerializedForm<E>(ImmutableMultiset.this);
418    }
419
420    @GwtIncompatible
421    @J2ktIncompatible
422        private void readObject(ObjectInputStream stream) throws InvalidObjectException {
423      throw new InvalidObjectException("Use EntrySetSerializedForm");
424    }
425
426    @GwtIncompatible @J2ktIncompatible private static final long serialVersionUID = 0;
427  }
428
429  @GwtIncompatible
430  @J2ktIncompatible
431  private static final class EntrySetSerializedForm<E> implements Serializable {
432    final ImmutableMultiset<E> multiset;
433
434    EntrySetSerializedForm(ImmutableMultiset<E> multiset) {
435      this.multiset = multiset;
436    }
437
438        Object readResolve() {
439      return multiset.entrySet();
440    }
441  }
442
443  @GwtIncompatible
444  @J2ktIncompatible
445  @Override
446    Object writeReplace() {
447    return new SerializedForm(this);
448  }
449
450  @GwtIncompatible
451  @J2ktIncompatible
452    private void readObject(ObjectInputStream stream) throws InvalidObjectException {
453    throw new InvalidObjectException("Use SerializedForm");
454  }
455
456  /**
457   * Returns a new builder. The generated builder is equivalent to the builder created by the {@link
458   * Builder} constructor.
459   */
460  public static <E> Builder<E> builder() {
461    return new Builder<>();
462  }
463
464  /**
465   * A builder for creating immutable multiset instances, especially {@code public static final}
466   * multisets ("constant multisets"). Example:
467   *
468   * {@snippet :
469   * public static final ImmutableMultiset<Bean> BEANS =
470   *     new ImmutableMultiset.Builder<Bean>()
471   *         .addCopies(Bean.COCOA, 4)
472   *         .addCopies(Bean.GARDEN, 6)
473   *         .addCopies(Bean.RED, 8)
474   *         .addCopies(Bean.BLACK_EYED, 10)
475   *         .build();
476   * }
477   *
478   * <p>Builder instances can be reused; it is safe to call {@link #build} multiple times to build
479   * multiple multisets in series.
480   *
481   * @since 2.0
482   */
483  public static class Builder<E> extends ImmutableCollection.Builder<E> {
484    final Multiset<E> contents;
485
486    /**
487     * Creates a new builder. The returned builder is equivalent to the builder generated by {@link
488     * ImmutableMultiset#builder}.
489     */
490    public Builder() {
491      this(LinkedHashMultiset.create());
492    }
493
494    Builder(Multiset<E> contents) {
495      this.contents = contents;
496    }
497
498    /**
499     * Adds {@code element} to the {@code ImmutableMultiset}.
500     *
501     * @param element the element to add
502     * @return this {@code Builder} object
503     * @throws NullPointerException if {@code element} is null
504     */
505    @CanIgnoreReturnValue
506    @Override
507    public Builder<E> add(E element) {
508      contents.add(checkNotNull(element));
509      return this;
510    }
511
512    /**
513     * Adds each element of {@code elements} to the {@code ImmutableMultiset}.
514     *
515     * @param elements the elements to add
516     * @return this {@code Builder} object
517     * @throws NullPointerException if {@code elements} is null or contains a null element
518     */
519    @CanIgnoreReturnValue
520    @Override
521    public Builder<E> add(E... elements) {
522      super.add(elements);
523      return this;
524    }
525
526    /**
527     * Adds a number of occurrences of an element to this {@code ImmutableMultiset}.
528     *
529     * @param element the element to add
530     * @param occurrences the number of occurrences of the element to add. May be zero, in which
531     *     case no change will be made.
532     * @return this {@code Builder} object
533     * @throws NullPointerException if {@code element} is null
534     * @throws IllegalArgumentException if {@code occurrences} is negative, or if this operation
535     *     would result in more than {@link Integer#MAX_VALUE} occurrences of the element
536     */
537    @CanIgnoreReturnValue
538    public Builder<E> addCopies(E element, int occurrences) {
539      contents.add(checkNotNull(element), occurrences);
540      return this;
541    }
542
543    /**
544     * Adds or removes the necessary occurrences of an element such that the element attains the
545     * desired count.
546     *
547     * @param element the element to add or remove occurrences of
548     * @param count the desired count of the element in this multiset
549     * @return this {@code Builder} object
550     * @throws NullPointerException if {@code element} is null
551     * @throws IllegalArgumentException if {@code count} is negative
552     */
553    @CanIgnoreReturnValue
554    public Builder<E> setCount(E element, int count) {
555      contents.setCount(checkNotNull(element), count);
556      return this;
557    }
558
559    /**
560     * Adds each element of {@code elements} to the {@code ImmutableMultiset}.
561     *
562     * @param elements the {@code Iterable} to add to the {@code ImmutableMultiset}
563     * @return this {@code Builder} object
564     * @throws NullPointerException if {@code elements} is null or contains a null element
565     */
566    @CanIgnoreReturnValue
567    @Override
568    public Builder<E> addAll(Iterable<? extends E> elements) {
569      if (elements instanceof Multiset) {
570        Multiset<? extends E> multiset = (Multiset<? extends E>) elements;
571        multiset.forEachEntry((e, n) -> contents.add(checkNotNull(e), n));
572      } else {
573        super.addAll(elements);
574      }
575      return this;
576    }
577
578    /**
579     * Adds each element of {@code elements} to the {@code ImmutableMultiset}.
580     *
581     * @param elements the elements to add to the {@code ImmutableMultiset}
582     * @return this {@code Builder} object
583     * @throws NullPointerException if {@code elements} is null or contains a null element
584     */
585    @CanIgnoreReturnValue
586    @Override
587    public Builder<E> addAll(Iterator<? extends E> elements) {
588      super.addAll(elements);
589      return this;
590    }
591
592    /**
593     * Returns a newly-created {@code ImmutableMultiset} based on the contents of the {@code
594     * Builder}.
595     */
596    @Override
597    public ImmutableMultiset<E> build() {
598      return copyOf(contents);
599    }
600
601    @VisibleForTesting
602    ImmutableMultiset<E> buildJdkBacked() {
603      if (contents.isEmpty()) {
604        return of();
605      }
606      return JdkBackedImmutableMultiset.create(contents.entrySet());
607    }
608  }
609
610  static final class ElementSet<E> extends IndexedImmutableSet<E> {
611    private final List<Entry<E>> entries;
612    // TODO(cpovirk): @Weak?
613    private final Multiset<E> delegate;
614
615    ElementSet(List<Entry<E>> entries, Multiset<E> delegate) {
616      this.entries = entries;
617      this.delegate = delegate;
618    }
619
620    @Override
621    E get(int index) {
622      return entries.get(index).getElement();
623    }
624
625    @Override
626    public boolean contains(@Nullable Object object) {
627      return delegate.contains(object);
628    }
629
630    @Override
631    boolean isPartialView() {
632      return true;
633    }
634
635    @Override
636    public int size() {
637      return entries.size();
638    }
639
640    // redeclare to help optimizers with b/310253115
641    @SuppressWarnings("RedundantOverride")
642    @Override
643    @J2ktIncompatible
644    @GwtIncompatible
645        Object writeReplace() {
646      return super.writeReplace();
647    }
648  }
649
650  @J2ktIncompatible
651  static final class SerializedForm implements Serializable {
652    final Object[] elements;
653    final int[] counts;
654
655    // "extends Object" works around https://github.com/typetools/checker-framework/issues/3013
656    SerializedForm(Multiset<? extends Object> multiset) {
657      int distinct = multiset.entrySet().size();
658      elements = new Object[distinct];
659      counts = new int[distinct];
660      int i = 0;
661      for (Entry<? extends Object> entry : multiset.entrySet()) {
662        elements[i] = entry.getElement();
663        counts[i] = entry.getCount();
664        i++;
665      }
666    }
667
668    Object readResolve() {
669      LinkedHashMultiset<Object> multiset = LinkedHashMultiset.create(elements.length);
670      for (int i = 0; i < elements.length; i++) {
671        multiset.add(elements[i], counts[i]);
672      }
673      return copyOf(multiset);
674    }
675
676    @GwtIncompatible private static final long serialVersionUID = 0;
677  }
678
679  @GwtIncompatible @J2ktIncompatible   private static final long serialVersionUID = 0xcafebabe;
680}