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.Beta;
022import com.google.common.annotations.GwtCompatible;
023import com.google.common.annotations.GwtIncompatible;
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.function.Function;
033import java.util.function.ToIntFunction;
034import java.util.stream.Collector;
035import javax.annotation.Nullable;
036
037/**
038 * A {@link Multiset} whose contents will never change, with many other important properties
039 * detailed at {@link ImmutableCollection}.
040 *
041 * <p><b>Grouped iteration.</b> In all current implementations, duplicate elements always appear
042 * consecutively when iterating. Elements iterate in order by the <i>first</i> appearance of
043 * that element when the multiset was created.
044 *
045 * <p>See the Guava User Guide article on <a href=
046 * "https://github.com/google/guava/wiki/ImmutableCollectionsExplained">
047 * 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
060   * {@code ImmutableMultiset}.  Elements iterate in order by the <i>first</i> appearance of that
061   * element in encounter order.
062   *
063   * @since 21.0
064   */
065  @Beta
066  public static <E> Collector<E, ?, ImmutableMultiset<E>> toImmutableMultiset() {
067    return 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    checkNotNull(elementFunction);
084    checkNotNull(countFunction);
085    return Collector.of(
086        LinkedHashMultiset::create,
087        (multiset, t) ->
088            multiset.add(checkNotNull(elementFunction.apply(t)), countFunction.applyAsInt(t)),
089        (multiset1, multiset2) -> {
090          multiset1.addAll(multiset2);
091          return multiset1;
092        },
093        (Multiset<E> multiset) -> copyFromEntries(multiset.entrySet()));
094  }
095
096  /**
097   * Returns the empty immutable multiset.
098   */
099  @SuppressWarnings("unchecked") // all supported methods are covariant
100  public static <E> ImmutableMultiset<E> of() {
101    return (ImmutableMultiset<E>) RegularImmutableMultiset.EMPTY;
102  }
103
104  /**
105   * Returns an immutable multiset containing a single element.
106   *
107   * @throws NullPointerException if {@code element} is null
108   * @since 6.0 (source-compatible since 2.0)
109   */
110  @SuppressWarnings("unchecked") // generic array created but never written
111  public static <E> ImmutableMultiset<E> of(E element) {
112    return copyFromElements(element);
113  }
114
115  /**
116   * Returns an immutable multiset containing the given elements, in order.
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) {
123    return copyFromElements(e1, e2);
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) {
135    return copyFromElements(e1, e2, e3);
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) {
147    return copyFromElements(e1, e2, e3, e4);
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) {
159    return copyFromElements(e1, e2, e3, e4, e5);
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 element is null
167   * @since 6.0 (source-compatible since 2.0)
168   */
169  @SuppressWarnings("unchecked") //
170  public static <E> ImmutableMultiset<E> of(E e1, E e2, E e3, E e4, E e5, E e6, E... others) {
171    return new Builder<E>().add(e1).add(e2).add(e3).add(e4).add(e5).add(e6).add(others).build();
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   * @since 6.0
180   */
181  public static <E> ImmutableMultiset<E> copyOf(E[] elements) {
182    return copyFromElements(elements);
183  }
184
185  /**
186   * Returns an immutable multiset containing the given elements, in the "grouped iteration order"
187   * described in the class documentation.
188   *
189   * @throws NullPointerException if any of {@code elements} is null
190   */
191  public static <E> ImmutableMultiset<E> copyOf(Iterable<? extends E> elements) {
192    if (elements instanceof ImmutableMultiset) {
193      @SuppressWarnings("unchecked") // all supported methods are covariant
194      ImmutableMultiset<E> result = (ImmutableMultiset<E>) elements;
195      if (!result.isPartialView()) {
196        return result;
197      }
198    }
199
200    Multiset<? extends E> multiset =
201        (elements instanceof Multiset)
202            ? Multisets.cast(elements)
203            : LinkedHashMultiset.create(elements);
204
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 new RegularImmutableMultiset<E>(entries);
220    }
221  }
222
223  /**
224   * Returns an immutable multiset containing the given elements, in the "grouped iteration order"
225   * described in the class documentation.
226   *
227   * @throws NullPointerException if any of {@code elements} is null
228   */
229  public static <E> ImmutableMultiset<E> copyOf(Iterator<? extends E> elements) {
230    Multiset<E> multiset = LinkedHashMultiset.create();
231    Iterators.addAll(multiset, elements);
232    return copyFromEntries(multiset.entrySet());
233  }
234
235  ImmutableMultiset() {}
236
237  @Override
238  public UnmodifiableIterator<E> iterator() {
239    final Iterator<Entry<E>> entryIterator = entrySet().iterator();
240    return new UnmodifiableIterator<E>() {
241      int remaining;
242      E element;
243
244      @Override
245      public boolean hasNext() {
246        return (remaining > 0) || entryIterator.hasNext();
247      }
248
249      @Override
250      public E next() {
251        if (remaining <= 0) {
252          Entry<E> entry = entryIterator.next();
253          element = entry.getElement();
254          remaining = entry.getCount();
255        }
256        remaining--;
257        return element;
258      }
259    };
260  }
261
262  @LazyInit
263  private transient ImmutableList<E> asList;
264
265  @Override
266  public ImmutableList<E> asList() {
267    ImmutableList<E> result = asList;
268    return (result == null) ? asList = super.asList() : result;
269  }
270
271  @Override
272  public boolean contains(@Nullable Object object) {
273    return count(object) > 0;
274  }
275
276  /**
277   * Guaranteed to throw an exception and leave the collection unmodified.
278   *
279   * @throws UnsupportedOperationException always
280   * @deprecated Unsupported operation.
281   */
282  @CanIgnoreReturnValue
283  @Deprecated
284  @Override
285  public final int add(E element, int occurrences) {
286    throw new UnsupportedOperationException();
287  }
288
289  /**
290   * Guaranteed to throw an exception and leave the collection unmodified.
291   *
292   * @throws UnsupportedOperationException always
293   * @deprecated Unsupported operation.
294   */
295  @CanIgnoreReturnValue
296  @Deprecated
297  @Override
298  public final int remove(Object element, int occurrences) {
299    throw new UnsupportedOperationException();
300  }
301
302  /**
303   * Guaranteed to throw an exception and leave the collection unmodified.
304   *
305   * @throws UnsupportedOperationException always
306   * @deprecated Unsupported operation.
307   */
308  @CanIgnoreReturnValue
309  @Deprecated
310  @Override
311  public final int setCount(E element, int count) {
312    throw new UnsupportedOperationException();
313  }
314
315  /**
316   * Guaranteed to throw an exception and leave the collection unmodified.
317   *
318   * @throws UnsupportedOperationException always
319   * @deprecated Unsupported operation.
320   */
321  @CanIgnoreReturnValue
322  @Deprecated
323  @Override
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(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(@Nullable 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
358  private transient ImmutableSet<Entry<E>> entrySet;
359
360  @Override
361  public ImmutableSet<Entry<E>> entrySet() {
362    ImmutableSet<Entry<E>> es = entrySet;
363    return (es == null) ? (entrySet = createEntrySet()) : es;
364  }
365
366  private final ImmutableSet<Entry<E>> createEntrySet() {
367    return isEmpty() ? ImmutableSet.<Entry<E>>of() : new EntrySet();
368  }
369
370  abstract Entry<E> getEntry(int index);
371
372  @WeakOuter
373  private final class EntrySet extends ImmutableSet.Indexed<Entry<E>> {
374    @Override
375    boolean isPartialView() {
376      return ImmutableMultiset.this.isPartialView();
377    }
378
379    @Override
380    Entry<E> get(int index) {
381      return getEntry(index);
382    }
383
384    @Override
385    public int size() {
386      return elementSet().size();
387    }
388
389    @Override
390    public boolean contains(Object o) {
391      if (o instanceof Entry) {
392        Entry<?> entry = (Entry<?>) o;
393        if (entry.getCount() <= 0) {
394          return false;
395        }
396        int count = count(entry.getElement());
397        return count == entry.getCount();
398      }
399      return false;
400    }
401
402    @Override
403    public int hashCode() {
404      return ImmutableMultiset.this.hashCode();
405    }
406
407    // We can't label this with @Override, because it doesn't override anything
408    // in the GWT emulated version.
409    // TODO(cpovirk): try making all copies of this method @GwtIncompatible instead
410    Object writeReplace() {
411      return new EntrySetSerializedForm<E>(ImmutableMultiset.this);
412    }
413
414    private static final long serialVersionUID = 0;
415  }
416
417  static class EntrySetSerializedForm<E> implements Serializable {
418    final ImmutableMultiset<E> multiset;
419
420    EntrySetSerializedForm(ImmutableMultiset<E> multiset) {
421      this.multiset = multiset;
422    }
423
424    Object readResolve() {
425      return multiset.entrySet();
426    }
427  }
428
429  private static class SerializedForm implements Serializable {
430    final Object[] elements;
431    final int[] counts;
432
433    SerializedForm(Multiset<?> multiset) {
434      int distinct = multiset.entrySet().size();
435      elements = new Object[distinct];
436      counts = new int[distinct];
437      int i = 0;
438      for (Entry<?> entry : multiset.entrySet()) {
439        elements[i] = entry.getElement();
440        counts[i] = entry.getCount();
441        i++;
442      }
443    }
444
445    Object readResolve() {
446      LinkedHashMultiset<Object> multiset = LinkedHashMultiset.create(elements.length);
447      for (int i = 0; i < elements.length; i++) {
448        multiset.add(elements[i], counts[i]);
449      }
450      return ImmutableMultiset.copyOf(multiset);
451    }
452
453    private static final long serialVersionUID = 0;
454  }
455
456  // We can't label this with @Override, because it doesn't override anything
457  // in the GWT emulated version.
458  Object writeReplace() {
459    return new SerializedForm(this);
460  }
461
462  /**
463   * Returns a new builder. The generated builder is equivalent to the builder
464   * created by the {@link Builder} constructor.
465   */
466  public static <E> Builder<E> builder() {
467    return new Builder<E>();
468  }
469
470  /**
471   * A builder for creating immutable multiset instances, especially {@code
472   * public static final} multisets ("constant multisets"). Example:
473   * <pre> {@code
474   *
475   *   public static final ImmutableMultiset<Bean> BEANS =
476   *       new ImmutableMultiset.Builder<Bean>()
477   *           .addCopies(Bean.COCOA, 4)
478   *           .addCopies(Bean.GARDEN, 6)
479   *           .addCopies(Bean.RED, 8)
480   *           .addCopies(Bean.BLACK_EYED, 10)
481   *           .build();}</pre>
482   *
483   * <p>Builder instances can be reused; it is safe to call {@link #build} multiple
484   * times to build multiple multisets in series.
485   *
486   * @since 2.0
487   */
488  public static class Builder<E> extends ImmutableCollection.Builder<E> {
489    final Multiset<E> contents;
490
491    /**
492     * Creates a new builder. The returned builder is equivalent to the builder
493     * generated by {@link ImmutableMultiset#builder}.
494     */
495    public Builder() {
496      this(LinkedHashMultiset.<E>create());
497    }
498
499    Builder(Multiset<E> contents) {
500      this.contents = contents;
501    }
502
503    /**
504     * Adds {@code element} to the {@code ImmutableMultiset}.
505     *
506     * @param element the element to add
507     * @return this {@code Builder} object
508     * @throws NullPointerException if {@code element} is null
509     */
510    @CanIgnoreReturnValue
511    @Override
512    public Builder<E> add(E element) {
513      contents.add(checkNotNull(element));
514      return this;
515    }
516
517    /**
518     * Adds a number of occurrences of an element to this {@code
519     * ImmutableMultiset}.
520     *
521     * @param element the element to add
522     * @param occurrences the number of occurrences of the element to add. May
523     *     be zero, in which case no change will be made.
524     * @return this {@code Builder} object
525     * @throws NullPointerException if {@code element} is null
526     * @throws IllegalArgumentException if {@code occurrences} is negative, or
527     *     if this operation would result in more than {@link Integer#MAX_VALUE}
528     *     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
538     * element attains the 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 elements to add
556     * @return this {@code Builder} object
557     * @throws NullPointerException if {@code elements} is null or contains a
558     *     null element
559     */
560    @CanIgnoreReturnValue
561    @Override
562    public Builder<E> add(E... elements) {
563      super.add(elements);
564      return this;
565    }
566
567    /**
568     * Adds each element of {@code elements} to the {@code ImmutableMultiset}.
569     *
570     * @param elements the {@code Iterable} to add to the {@code
571     *     ImmutableMultiset}
572     * @return this {@code Builder} object
573     * @throws NullPointerException if {@code elements} is null or contains a
574     *     null element
575     */
576    @CanIgnoreReturnValue
577    @Override
578    public Builder<E> addAll(Iterable<? extends E> elements) {
579      if (elements instanceof Multiset) {
580        Multiset<? extends E> multiset = Multisets.cast(elements);
581        for (Entry<? extends E> entry : multiset.entrySet()) {
582          addCopies(entry.getElement(), entry.getCount());
583        }
584      } else {
585        super.addAll(elements);
586      }
587      return this;
588    }
589
590    /**
591     * Adds each element of {@code elements} to the {@code ImmutableMultiset}.
592     *
593     * @param elements the elements to add to the {@code ImmutableMultiset}
594     * @return this {@code Builder} object
595     * @throws NullPointerException if {@code elements} is null or contains a
596     *     null element
597     */
598    @CanIgnoreReturnValue
599    @Override
600    public Builder<E> addAll(Iterator<? extends E> elements) {
601      super.addAll(elements);
602      return this;
603    }
604
605    /**
606     * Returns a newly-created {@code ImmutableMultiset} based on the contents
607     * of the {@code Builder}.
608     */
609    @Override
610    public ImmutableMultiset<E> build() {
611      return copyOf(contents);
612    }
613  }
614}