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.common.annotations.VisibleForTesting;
026import com.google.errorprone.annotations.CanIgnoreReturnValue;
027import com.google.errorprone.annotations.DoNotCall;
028import com.google.errorprone.annotations.concurrent.LazyInit;
029import com.google.j2objc.annotations.WeakOuter;
030import java.io.InvalidObjectException;
031import java.io.ObjectInputStream;
032import java.io.Serializable;
033import java.util.Arrays;
034import java.util.Collection;
035import java.util.Collections;
036import java.util.Iterator;
037import java.util.List;
038import java.util.function.Function;
039import java.util.function.ToIntFunction;
040import java.util.stream.Collector;
041import javax.annotation.CheckForNull;
042import org.checkerframework.checker.nullness.qual.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(serializable = true, emulated = true)
060@SuppressWarnings("serial") // we're overriding default serialization
061@ElementTypesAreNonnullByDefault
062public abstract class ImmutableMultiset<E> extends ImmutableMultisetGwtSerializationDependencies<E>
063    implements Multiset<E> {
064
065  /**
066   * Returns a {@code Collector} that accumulates the input elements into a new {@code
067   * ImmutableMultiset}. Elements iterate in order by the <i>first</i> appearance of that element in
068   * encounter order.
069   *
070   * @since 21.0
071   */
072  public static <E> Collector<E, ?, ImmutableMultiset<E>> toImmutableMultiset() {
073    return CollectCollectors.toImmutableMultiset(Function.identity(), e -> 1);
074  }
075
076  /**
077   * Returns a {@code Collector} that accumulates elements into an {@code ImmutableMultiset} whose
078   * elements are the result of applying {@code elementFunction} to the inputs, with counts equal to
079   * the result of applying {@code countFunction} to the inputs.
080   *
081   * <p>If the mapped elements contain duplicates (according to {@link Object#equals}), the first
082   * occurrence in encounter order appears in the resulting multiset, with count equal to the sum of
083   * the outputs of {@code countFunction.applyAsInt(t)} for each {@code t} mapped to that element.
084   *
085   * @since 22.0
086   */
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 {@code element} is null
108   * @since 6.0 (source-compatible since 2.0)
109   */
110  public static <E> ImmutableMultiset<E> of(E element) {
111    return copyFromElements(element);
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
194    Multiset<? extends E> multiset =
195        (elements instanceof Multiset)
196            ? Multisets.cast(elements)
197            : LinkedHashMultiset.create(elements);
198
199    return copyFromEntries(multiset.entrySet());
200  }
201
202  /**
203   * Returns an immutable multiset containing the given elements, in the "grouped iteration order"
204   * described in the class documentation.
205   *
206   * @throws NullPointerException if any of {@code elements} is null
207   */
208  public static <E> ImmutableMultiset<E> copyOf(Iterator<? extends E> elements) {
209    Multiset<E> multiset = LinkedHashMultiset.create();
210    Iterators.addAll(multiset, elements);
211    return copyFromEntries(multiset.entrySet());
212  }
213
214  private static <E> ImmutableMultiset<E> copyFromElements(E... elements) {
215    Multiset<E> multiset = LinkedHashMultiset.create();
216    Collections.addAll(multiset, elements);
217    return copyFromEntries(multiset.entrySet());
218  }
219
220  static <E> ImmutableMultiset<E> copyFromEntries(
221      Collection<? extends Entry<? extends E>> entries) {
222    if (entries.isEmpty()) {
223      return of();
224    } else {
225      return RegularImmutableMultiset.create(entries);
226    }
227  }
228
229  ImmutableMultiset() {}
230
231  @Override
232  public UnmodifiableIterator<E> iterator() {
233    final Iterator<Entry<E>> entryIterator = entrySet().iterator();
234    return new UnmodifiableIterator<E>() {
235      int remaining;
236      @CheckForNull E element;
237
238      @Override
239      public boolean hasNext() {
240        return (remaining > 0) || entryIterator.hasNext();
241      }
242
243      @Override
244      public E next() {
245        if (remaining <= 0) {
246          Entry<E> entry = entryIterator.next();
247          element = entry.getElement();
248          remaining = entry.getCount();
249        }
250        remaining--;
251        /*
252         * requireNonNull is safe because `remaining` starts at 0, forcing us to initialize
253         * `element` above. After that, we never clear it.
254         */
255        return requireNonNull(element);
256      }
257    };
258  }
259
260  @LazyInit @CheckForNull 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(@CheckForNull 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  @DoNotCall("Always throws UnsupportedOperationException")
283  public final int add(E element, int occurrences) {
284    throw new UnsupportedOperationException();
285  }
286
287  /**
288   * Guaranteed to throw an exception and leave the collection unmodified.
289   *
290   * @throws UnsupportedOperationException always
291   * @deprecated Unsupported operation.
292   */
293  @CanIgnoreReturnValue
294  @Deprecated
295  @Override
296  @DoNotCall("Always throws UnsupportedOperationException")
297  public final int remove(@CheckForNull Object element, int occurrences) {
298    throw new UnsupportedOperationException();
299  }
300
301  /**
302   * Guaranteed to throw an exception and leave the collection unmodified.
303   *
304   * @throws UnsupportedOperationException always
305   * @deprecated Unsupported operation.
306   */
307  @CanIgnoreReturnValue
308  @Deprecated
309  @Override
310  @DoNotCall("Always throws UnsupportedOperationException")
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  @DoNotCall("Always throws UnsupportedOperationException")
325  public final boolean setCount(E element, int oldCount, int newCount) {
326    throw new UnsupportedOperationException();
327  }
328
329  @GwtIncompatible // not present in emulated superclass
330  @Override
331  int copyIntoArray(@Nullable Object[] dst, int offset) {
332    for (Multiset.Entry<E> entry : entrySet()) {
333      Arrays.fill(dst, offset, offset + entry.getCount(), entry.getElement());
334      offset += entry.getCount();
335    }
336    return offset;
337  }
338
339  @Override
340  public boolean equals(@CheckForNull Object object) {
341    return Multisets.equalsImpl(this, object);
342  }
343
344  @Override
345  public int hashCode() {
346    return Sets.hashCodeImpl(entrySet());
347  }
348
349  @Override
350  public String toString() {
351    return entrySet().toString();
352  }
353
354  /** @since 21.0 (present with return type {@code Set} since 2.0) */
355  @Override
356  public abstract ImmutableSet<E> elementSet();
357
358  @LazyInit @CheckForNull 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 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 IndexedImmutableSet<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(@CheckForNull 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    @GwtIncompatible
408    @J2ktIncompatible
409    @Override
410    Object writeReplace() {
411      return new EntrySetSerializedForm<E>(ImmutableMultiset.this);
412    }
413
414    @GwtIncompatible
415    @J2ktIncompatible
416    private void readObject(ObjectInputStream stream) throws InvalidObjectException {
417      throw new InvalidObjectException("Use EntrySetSerializedForm");
418    }
419
420    @J2ktIncompatible private static final long serialVersionUID = 0;
421  }
422
423  @GwtIncompatible
424  @J2ktIncompatible
425  static class EntrySetSerializedForm<E> implements Serializable {
426    final ImmutableMultiset<E> multiset;
427
428    EntrySetSerializedForm(ImmutableMultiset<E> multiset) {
429      this.multiset = multiset;
430    }
431
432    Object readResolve() {
433      return multiset.entrySet();
434    }
435  }
436
437  @GwtIncompatible
438  @J2ktIncompatible
439  @Override
440  Object writeReplace() {
441    return new SerializedForm(this);
442  }
443
444  @GwtIncompatible
445  @J2ktIncompatible
446  private void readObject(ObjectInputStream stream) throws InvalidObjectException {
447    throw new InvalidObjectException("Use SerializedForm");
448  }
449
450  /**
451   * Returns a new builder. The generated builder is equivalent to the builder created by the {@link
452   * Builder} constructor.
453   */
454  public static <E> Builder<E> builder() {
455    return new Builder<E>();
456  }
457
458  /**
459   * A builder for creating immutable multiset instances, especially {@code public static final}
460   * multisets ("constant multisets"). Example:
461   *
462   * <pre>{@code
463   * public static final ImmutableMultiset<Bean> BEANS =
464   *     new ImmutableMultiset.Builder<Bean>()
465   *         .addCopies(Bean.COCOA, 4)
466   *         .addCopies(Bean.GARDEN, 6)
467   *         .addCopies(Bean.RED, 8)
468   *         .addCopies(Bean.BLACK_EYED, 10)
469   *         .build();
470   * }</pre>
471   *
472   * <p>Builder instances can be reused; it is safe to call {@link #build} multiple times to build
473   * multiple multisets in series.
474   *
475   * @since 2.0
476   */
477  public static class Builder<E> extends ImmutableCollection.Builder<E> {
478    final Multiset<E> contents;
479
480    /**
481     * Creates a new builder. The returned builder is equivalent to the builder generated by {@link
482     * ImmutableMultiset#builder}.
483     */
484    public Builder() {
485      this(LinkedHashMultiset.<E>create());
486    }
487
488    Builder(Multiset<E> contents) {
489      this.contents = contents;
490    }
491
492    /**
493     * Adds {@code element} to the {@code ImmutableMultiset}.
494     *
495     * @param element the element to add
496     * @return this {@code Builder} object
497     * @throws NullPointerException if {@code element} is null
498     */
499    @CanIgnoreReturnValue
500    @Override
501    public Builder<E> add(E element) {
502      contents.add(checkNotNull(element));
503      return this;
504    }
505
506    /**
507     * Adds each element of {@code elements} to the {@code ImmutableMultiset}.
508     *
509     * @param elements the elements to add
510     * @return this {@code Builder} object
511     * @throws NullPointerException if {@code elements} is null or contains a null element
512     */
513    @CanIgnoreReturnValue
514    @Override
515    public Builder<E> add(E... elements) {
516      super.add(elements);
517      return this;
518    }
519
520    /**
521     * Adds a number of occurrences of an element to this {@code ImmutableMultiset}.
522     *
523     * @param element the element to add
524     * @param occurrences the number of occurrences of the element to add. May be zero, in which
525     *     case no change will be made.
526     * @return this {@code Builder} object
527     * @throws NullPointerException if {@code element} is null
528     * @throws IllegalArgumentException if {@code occurrences} is negative, or if this operation
529     *     would result in more than {@link Integer#MAX_VALUE} occurrences of the element
530     */
531    @CanIgnoreReturnValue
532    public Builder<E> addCopies(E element, int occurrences) {
533      contents.add(checkNotNull(element), occurrences);
534      return this;
535    }
536
537    /**
538     * Adds or removes the necessary occurrences of an element such that the element attains the
539     * desired count.
540     *
541     * @param element the element to add or remove occurrences of
542     * @param count the desired count of the element in this multiset
543     * @return this {@code Builder} object
544     * @throws NullPointerException if {@code element} is null
545     * @throws IllegalArgumentException if {@code count} is negative
546     */
547    @CanIgnoreReturnValue
548    public Builder<E> setCount(E element, int count) {
549      contents.setCount(checkNotNull(element), count);
550      return this;
551    }
552
553    /**
554     * Adds each element of {@code elements} to the {@code ImmutableMultiset}.
555     *
556     * @param elements the {@code Iterable} 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(Iterable<? extends E> elements) {
563      if (elements instanceof Multiset) {
564        Multiset<? extends E> multiset = Multisets.cast(elements);
565        multiset.forEachEntry((e, n) -> contents.add(checkNotNull(e), n));
566      } else {
567        super.addAll(elements);
568      }
569      return this;
570    }
571
572    /**
573     * Adds each element of {@code elements} to the {@code ImmutableMultiset}.
574     *
575     * @param elements the elements to add to the {@code ImmutableMultiset}
576     * @return this {@code Builder} object
577     * @throws NullPointerException if {@code elements} is null or contains a null element
578     */
579    @CanIgnoreReturnValue
580    @Override
581    public Builder<E> addAll(Iterator<? extends E> elements) {
582      super.addAll(elements);
583      return this;
584    }
585
586    /**
587     * Returns a newly-created {@code ImmutableMultiset} based on the contents of the {@code
588     * Builder}.
589     */
590    @Override
591    public ImmutableMultiset<E> build() {
592      return copyOf(contents);
593    }
594
595    @VisibleForTesting
596    ImmutableMultiset<E> buildJdkBacked() {
597      if (contents.isEmpty()) {
598        return of();
599      }
600      return JdkBackedImmutableMultiset.create(contents.entrySet());
601    }
602  }
603
604  static final class ElementSet<E> extends ImmutableSet.Indexed<E> {
605    private final List<Entry<E>> entries;
606    // TODO(cpovirk): @Weak?
607    private final Multiset<E> delegate;
608
609    ElementSet(List<Entry<E>> entries, Multiset<E> delegate) {
610      this.entries = entries;
611      this.delegate = delegate;
612    }
613
614    @Override
615    E get(int index) {
616      return entries.get(index).getElement();
617    }
618
619    @Override
620    public boolean contains(@CheckForNull Object object) {
621      return delegate.contains(object);
622    }
623
624    @Override
625    boolean isPartialView() {
626      return true;
627    }
628
629    @Override
630    public int size() {
631      return entries.size();
632    }
633
634    // redeclare to help optimizers with b/310253115
635    @SuppressWarnings("RedundantOverride")
636    @Override
637    @J2ktIncompatible // serialization
638    @GwtIncompatible // serialization
639    Object writeReplace() {
640      return super.writeReplace();
641    }
642  }
643
644  @J2ktIncompatible
645  static final class SerializedForm implements Serializable {
646    final Object[] elements;
647    final int[] counts;
648
649    // "extends Object" works around https://github.com/typetools/checker-framework/issues/3013
650    SerializedForm(Multiset<? extends Object> multiset) {
651      int distinct = multiset.entrySet().size();
652      elements = new Object[distinct];
653      counts = new int[distinct];
654      int i = 0;
655      for (Entry<? extends Object> entry : multiset.entrySet()) {
656        elements[i] = entry.getElement();
657        counts[i] = entry.getCount();
658        i++;
659      }
660    }
661
662    Object readResolve() {
663      LinkedHashMultiset<Object> multiset = LinkedHashMultiset.create(elements.length);
664      for (int i = 0; i < elements.length; i++) {
665        multiset.add(elements[i], counts[i]);
666      }
667      return ImmutableMultiset.copyOf(multiset);
668    }
669
670    private static final long serialVersionUID = 0;
671  }
672
673  private static final long serialVersionUID = 0xcafebabe;
674}