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