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