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