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