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.common.annotations.VisibleForTesting;
025import com.google.errorprone.annotations.CanIgnoreReturnValue;
026import com.google.errorprone.annotations.concurrent.LazyInit;
027import com.google.j2objc.annotations.WeakOuter;
028import java.io.Serializable;
029import java.util.Arrays;
030import java.util.Collection;
031import java.util.Collections;
032import java.util.Iterator;
033import java.util.List;
034import java.util.function.Function;
035import java.util.function.ToIntFunction;
036import java.util.stream.Collector;
037import org.checkerframework.checker.nullness.qual.MonotonicNonNull;
038import org.checkerframework.checker.nullness.qual.Nullable;
039
040/**
041 * A {@link Multiset} whose contents will never change, with many other important properties
042 * detailed at {@link ImmutableCollection}.
043 *
044 * <p><b>Grouped iteration.</b> In all current implementations, duplicate elements always appear
045 * consecutively when iterating. Elements iterate in order by the <i>first</i> appearance of that
046 * element when the multiset was created.
047 *
048 * <p>See the Guava User Guide article on <a href=
049 * "https://github.com/google/guava/wiki/ImmutableCollectionsExplained"> immutable collections</a>.
050 *
051 * @author Jared Levy
052 * @author Louis Wasserman
053 * @since 2.0
054 */
055@GwtCompatible(serializable = true, emulated = true)
056@SuppressWarnings("serial") // we're overriding default serialization
057public abstract class ImmutableMultiset<E> extends ImmutableMultisetGwtSerializationDependencies<E>
058    implements Multiset<E> {
059
060  /**
061   * Returns a {@code Collector} that accumulates the input elements into a new {@code
062   * ImmutableMultiset}. Elements iterate in order by the <i>first</i> appearance of that element in
063   * encounter order.
064   *
065   * @since 21.0
066   */
067  @Beta
068  public static <E> Collector<E, ?, ImmutableMultiset<E>> toImmutableMultiset() {
069    return toImmutableMultiset(Function.identity(), e -> 1);
070  }
071
072  /**
073   * Returns a {@code Collector} that accumulates elements into an {@code ImmutableMultiset} whose
074   * elements are the result of applying {@code elementFunction} to the inputs, with counts equal to
075   * the result of applying {@code countFunction} to the inputs.
076   *
077   * <p>If the mapped elements contain duplicates (according to {@link Object#equals}), the first
078   * occurrence in encounter order appears in the resulting multiset, with count equal to the sum of
079   * the outputs of {@code countFunction.applyAsInt(t)} for each {@code t} mapped to that element.
080   *
081   * @since 22.0
082   */
083  public static <T, E> Collector<T, ?, ImmutableMultiset<E>> toImmutableMultiset(
084      Function<? super T, ? extends E> elementFunction, ToIntFunction<? super T> countFunction) {
085    checkNotNull(elementFunction);
086    checkNotNull(countFunction);
087    return Collector.of(
088        LinkedHashMultiset::create,
089        (multiset, t) ->
090            multiset.add(checkNotNull(elementFunction.apply(t)), countFunction.applyAsInt(t)),
091        (multiset1, multiset2) -> {
092          multiset1.addAll(multiset2);
093          return multiset1;
094        },
095        (Multiset<E> multiset) -> copyFromEntries(multiset.entrySet()));
096  }
097
098  /** Returns the empty immutable multiset. */
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  /**
209   * Returns an immutable multiset containing the given elements, in the "grouped iteration order"
210   * described in the class documentation.
211   *
212   * @throws NullPointerException if any of {@code elements} is null
213   */
214  public static <E> ImmutableMultiset<E> copyOf(Iterator<? extends E> elements) {
215    Multiset<E> multiset = LinkedHashMultiset.create();
216    Iterators.addAll(multiset, elements);
217    return copyFromEntries(multiset.entrySet());
218  }
219
220  private static <E> ImmutableMultiset<E> copyFromElements(E... elements) {
221    Multiset<E> multiset = LinkedHashMultiset.create();
222    Collections.addAll(multiset, elements);
223    return copyFromEntries(multiset.entrySet());
224  }
225
226  static <E> ImmutableMultiset<E> copyFromEntries(
227      Collection<? extends Entry<? extends E>> entries) {
228    if (entries.isEmpty()) {
229      return of();
230    } else {
231      return RegularImmutableMultiset.create(entries);
232    }
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      @MonotonicNonNull 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 private transient ImmutableList<E> asList;
263
264  @Override
265  public ImmutableList<E> asList() {
266    ImmutableList<E> result = asList;
267    return (result == null) ? asList = super.asList() : result;
268  }
269
270  @Override
271  public boolean contains(@Nullable Object object) {
272    return count(object) > 0;
273  }
274
275  /**
276   * Guaranteed to throw an exception and leave the collection unmodified.
277   *
278   * @throws UnsupportedOperationException always
279   * @deprecated Unsupported operation.
280   */
281  @CanIgnoreReturnValue
282  @Deprecated
283  @Override
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  public final int remove(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  public final int setCount(E element, int count) {
311    throw new UnsupportedOperationException();
312  }
313
314  /**
315   * Guaranteed to throw an exception and leave the collection unmodified.
316   *
317   * @throws UnsupportedOperationException always
318   * @deprecated Unsupported operation.
319   */
320  @CanIgnoreReturnValue
321  @Deprecated
322  @Override
323  public final boolean setCount(E element, int oldCount, int newCount) {
324    throw new UnsupportedOperationException();
325  }
326
327  @GwtIncompatible // not present in emulated superclass
328  @Override
329  int copyIntoArray(Object[] dst, int offset) {
330    for (Multiset.Entry<E> entry : entrySet()) {
331      Arrays.fill(dst, offset, offset + entry.getCount(), entry.getElement());
332      offset += entry.getCount();
333    }
334    return offset;
335  }
336
337  @Override
338  public boolean equals(@Nullable Object object) {
339    return Multisets.equalsImpl(this, object);
340  }
341
342  @Override
343  public int hashCode() {
344    return Sets.hashCodeImpl(entrySet());
345  }
346
347  @Override
348  public String toString() {
349    return entrySet().toString();
350  }
351
352  /** @since 21.0 (present with return type {@code Set} since 2.0) */
353  @Override
354  public abstract ImmutableSet<E> elementSet();
355
356  @LazyInit private transient ImmutableSet<Entry<E>> entrySet;
357
358  @Override
359  public ImmutableSet<Entry<E>> entrySet() {
360    ImmutableSet<Entry<E>> es = entrySet;
361    return (es == null) ? (entrySet = createEntrySet()) : es;
362  }
363
364  private ImmutableSet<Entry<E>> createEntrySet() {
365    return isEmpty() ? ImmutableSet.<Entry<E>>of() : new EntrySet();
366  }
367
368  abstract Entry<E> getEntry(int index);
369
370  @WeakOuter
371  private final class EntrySet extends IndexedImmutableSet<Entry<E>> {
372    @Override
373    boolean isPartialView() {
374      return ImmutableMultiset.this.isPartialView();
375    }
376
377    @Override
378    Entry<E> get(int index) {
379      return getEntry(index);
380    }
381
382    @Override
383    public int size() {
384      return elementSet().size();
385    }
386
387    @Override
388    public boolean contains(Object o) {
389      if (o instanceof Entry) {
390        Entry<?> entry = (Entry<?>) o;
391        if (entry.getCount() <= 0) {
392          return false;
393        }
394        int count = count(entry.getElement());
395        return count == entry.getCount();
396      }
397      return false;
398    }
399
400    @Override
401    public int hashCode() {
402      return ImmutableMultiset.this.hashCode();
403    }
404
405    @GwtIncompatible
406    @Override
407    Object writeReplace() {
408      return new EntrySetSerializedForm<E>(ImmutableMultiset.this);
409    }
410
411    private static final long serialVersionUID = 0;
412  }
413
414  @GwtIncompatible
415  static class EntrySetSerializedForm<E> implements Serializable {
416    final ImmutableMultiset<E> multiset;
417
418    EntrySetSerializedForm(ImmutableMultiset<E> multiset) {
419      this.multiset = multiset;
420    }
421
422    Object readResolve() {
423      return multiset.entrySet();
424    }
425  }
426
427  @GwtIncompatible
428  @Override
429  Object writeReplace() {
430    return new SerializedForm(this);
431  }
432
433  /**
434   * Returns a new builder. The generated builder is equivalent to the builder created by the {@link
435   * Builder} constructor.
436   */
437  public static <E> Builder<E> builder() {
438    return new Builder<E>();
439  }
440
441  /**
442   * A builder for creating immutable multiset instances, especially {@code public static final}
443   * multisets ("constant multisets"). Example:
444   *
445   * <pre>{@code
446   * public static final ImmutableMultiset<Bean> BEANS =
447   *     new ImmutableMultiset.Builder<Bean>()
448   *         .addCopies(Bean.COCOA, 4)
449   *         .addCopies(Bean.GARDEN, 6)
450   *         .addCopies(Bean.RED, 8)
451   *         .addCopies(Bean.BLACK_EYED, 10)
452   *         .build();
453   * }</pre>
454   *
455   * <p>Builder instances can be reused; it is safe to call {@link #build} multiple times to build
456   * multiple multisets in series.
457   *
458   * @since 2.0
459   */
460  public static class Builder<E> extends ImmutableCollection.Builder<E> {
461    final Multiset<E> contents;
462
463    /**
464     * Creates a new builder. The returned builder is equivalent to the builder generated by {@link
465     * ImmutableMultiset#builder}.
466     */
467    public Builder() {
468      this(LinkedHashMultiset.<E>create());
469    }
470
471    Builder(Multiset<E> contents) {
472      this.contents = contents;
473    }
474
475    /**
476     * Adds {@code element} to the {@code ImmutableMultiset}.
477     *
478     * @param element the element to add
479     * @return this {@code Builder} object
480     * @throws NullPointerException if {@code element} is null
481     */
482    @CanIgnoreReturnValue
483    @Override
484    public Builder<E> add(E element) {
485      contents.add(checkNotNull(element));
486      return this;
487    }
488
489    /**
490     * Adds each element of {@code elements} to the {@code ImmutableMultiset}.
491     *
492     * @param elements the elements to add
493     * @return this {@code Builder} object
494     * @throws NullPointerException if {@code elements} is null or contains a null element
495     */
496    @CanIgnoreReturnValue
497    @Override
498    public Builder<E> add(E... elements) {
499      super.add(elements);
500      return this;
501    }
502
503    /**
504     * Adds a number of occurrences of an element to this {@code ImmutableMultiset}.
505     *
506     * @param element the element to add
507     * @param occurrences the number of occurrences of the element to add. May be zero, in which
508     *     case no change will be made.
509     * @return this {@code Builder} object
510     * @throws NullPointerException if {@code element} is null
511     * @throws IllegalArgumentException if {@code occurrences} is negative, or if this operation
512     *     would result in more than {@link Integer#MAX_VALUE} occurrences of the element
513     */
514    @CanIgnoreReturnValue
515    public Builder<E> addCopies(E element, int occurrences) {
516      contents.add(checkNotNull(element), occurrences);
517      return this;
518    }
519
520    /**
521     * Adds or removes the necessary occurrences of an element such that the element attains the
522     * desired count.
523     *
524     * @param element the element to add or remove occurrences of
525     * @param count the desired count of the element in this multiset
526     * @return this {@code Builder} object
527     * @throws NullPointerException if {@code element} is null
528     * @throws IllegalArgumentException if {@code count} is negative
529     */
530    @CanIgnoreReturnValue
531    public Builder<E> setCount(E element, int count) {
532      contents.setCount(checkNotNull(element), count);
533      return this;
534    }
535
536    /**
537     * Adds each element of {@code elements} to the {@code ImmutableMultiset}.
538     *
539     * @param elements the {@code Iterable} to add to the {@code ImmutableMultiset}
540     * @return this {@code Builder} object
541     * @throws NullPointerException if {@code elements} is null or contains a null element
542     */
543    @CanIgnoreReturnValue
544    @Override
545    public Builder<E> addAll(Iterable<? extends E> elements) {
546      if (elements instanceof Multiset) {
547        Multiset<? extends E> multiset = Multisets.cast(elements);
548        multiset.forEachEntry((e, n) -> contents.add(checkNotNull(e), n));
549      } else {
550        super.addAll(elements);
551      }
552      return this;
553    }
554
555    /**
556     * Adds each element of {@code elements} to the {@code ImmutableMultiset}.
557     *
558     * @param elements the elements to add to the {@code ImmutableMultiset}
559     * @return this {@code Builder} object
560     * @throws NullPointerException if {@code elements} is null or contains a null element
561     */
562    @CanIgnoreReturnValue
563    @Override
564    public Builder<E> addAll(Iterator<? extends E> elements) {
565      super.addAll(elements);
566      return this;
567    }
568
569    /**
570     * Returns a newly-created {@code ImmutableMultiset} based on the contents of the {@code
571     * Builder}.
572     */
573    @Override
574    public ImmutableMultiset<E> build() {
575      return copyOf(contents);
576    }
577
578    @VisibleForTesting
579    ImmutableMultiset<E> buildJdkBacked() {
580      if (contents.isEmpty()) {
581        return of();
582      }
583      return JdkBackedImmutableMultiset.create(contents.entrySet());
584    }
585  }
586
587  static final class ElementSet<E> extends ImmutableSet.Indexed<E> {
588    private final List<Entry<E>> entries;
589    // TODO(cpovirk): @Weak?
590    private final Multiset<E> delegate;
591
592    ElementSet(List<Entry<E>> entries, Multiset<E> delegate) {
593      this.entries = entries;
594      this.delegate = delegate;
595    }
596
597    @Override
598    E get(int index) {
599      return entries.get(index).getElement();
600    }
601
602    @Override
603    public boolean contains(@Nullable Object object) {
604      return delegate.contains(object);
605    }
606
607    @Override
608    boolean isPartialView() {
609      return true;
610    }
611
612    @Override
613    public int size() {
614      return entries.size();
615    }
616  }
617
618  static final class SerializedForm implements Serializable {
619    final Object[] elements;
620    final int[] counts;
621
622    SerializedForm(Multiset<?> multiset) {
623      int distinct = multiset.entrySet().size();
624      elements = new Object[distinct];
625      counts = new int[distinct];
626      int i = 0;
627      for (Entry<?> 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}