Source code

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