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