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