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.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.InvalidObjectException;
030import java.io.ObjectInputStream;
031import java.io.Serializable;
032import java.util.Arrays;
033import java.util.Collection;
034import java.util.Iterator;
035import java.util.Set;
036import javax.annotation.CheckForNull;
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
056@ElementTypesAreNonnullByDefault
057public abstract class ImmutableMultiset<E> extends ImmutableMultisetGwtSerializationDependencies<E>
058    implements Multiset<E> {
059  /**
060   * Returns the empty immutable multiset.
061   *
062   * <p><b>Performance note:</b> the instance returned is a singleton.
063   */
064  @SuppressWarnings("unchecked") // all supported methods are covariant
065  public static <E> ImmutableMultiset<E> of() {
066    return (ImmutableMultiset<E>) RegularImmutableMultiset.EMPTY;
067  }
068
069  /**
070   * Returns an immutable multiset containing a single element.
071   *
072   * @throws NullPointerException if {@code element} is null
073   * @since 6.0 (source-compatible since 2.0)
074   */
075  public static <E> ImmutableMultiset<E> of(E element) {
076    return copyFromElements(element);
077  }
078
079  /**
080   * Returns an immutable multiset containing the given elements, in order.
081   *
082   * @throws NullPointerException if any element is null
083   * @since 6.0 (source-compatible since 2.0)
084   */
085  public static <E> ImmutableMultiset<E> of(E e1, E e2) {
086    return copyFromElements(e1, e2);
087  }
088
089  /**
090   * Returns an immutable multiset containing the given elements, in the "grouped iteration order"
091   * described in the class documentation.
092   *
093   * @throws NullPointerException if any element is null
094   * @since 6.0 (source-compatible since 2.0)
095   */
096  public static <E> ImmutableMultiset<E> of(E e1, E e2, E e3) {
097    return copyFromElements(e1, e2, e3);
098  }
099
100  /**
101   * Returns an immutable multiset containing the given elements, in the "grouped iteration order"
102   * described in the class documentation.
103   *
104   * @throws NullPointerException if any element is null
105   * @since 6.0 (source-compatible since 2.0)
106   */
107  public static <E> ImmutableMultiset<E> of(E e1, E e2, E e3, E e4) {
108    return copyFromElements(e1, e2, e3, e4);
109  }
110
111  /**
112   * Returns an immutable multiset containing the given elements, in the "grouped iteration order"
113   * described in the class documentation.
114   *
115   * @throws NullPointerException if any element is null
116   * @since 6.0 (source-compatible since 2.0)
117   */
118  public static <E> ImmutableMultiset<E> of(E e1, E e2, E e3, E e4, E e5) {
119    return copyFromElements(e1, e2, e3, e4, e5);
120  }
121
122  /**
123   * Returns an immutable multiset containing the given elements, in the "grouped iteration order"
124   * described in the class documentation.
125   *
126   * @throws NullPointerException if any element is null
127   * @since 6.0 (source-compatible since 2.0)
128   */
129  public static <E> ImmutableMultiset<E> of(E e1, E e2, E e3, E e4, E e5, E e6, E... others) {
130    return new Builder<E>().add(e1).add(e2).add(e3).add(e4).add(e5).add(e6).add(others).build();
131  }
132
133  /**
134   * Returns an immutable multiset containing the given elements, in the "grouped iteration order"
135   * described in the class documentation.
136   *
137   * @throws NullPointerException if any of {@code elements} is null
138   * @since 6.0
139   */
140  public static <E> ImmutableMultiset<E> copyOf(E[] elements) {
141    return copyFromElements(elements);
142  }
143
144  /**
145   * Returns an immutable multiset containing the given elements, in the "grouped iteration order"
146   * described in the class documentation.
147   *
148   * @throws NullPointerException if any of {@code elements} is null
149   */
150  public static <E> ImmutableMultiset<E> copyOf(Iterable<? extends E> elements) {
151    if (elements instanceof ImmutableMultiset) {
152      @SuppressWarnings("unchecked") // all supported methods are covariant
153      ImmutableMultiset<E> result = (ImmutableMultiset<E>) elements;
154      if (!result.isPartialView()) {
155        return result;
156      }
157    }
158    ImmutableMultiset.Builder<E> builder =
159        new ImmutableMultiset.Builder<E>(Multisets.inferDistinctElements(elements));
160    builder.addAll(elements);
161    return builder.build();
162  }
163
164  /**
165   * Returns an immutable multiset containing the given elements, in the "grouped iteration order"
166   * described in the class documentation.
167   *
168   * @throws NullPointerException if any of {@code elements} is null
169   */
170  public static <E> ImmutableMultiset<E> copyOf(Iterator<? extends E> elements) {
171    return new ImmutableMultiset.Builder<E>().addAll(elements).build();
172  }
173
174  private static <E> ImmutableMultiset<E> copyFromElements(E... elements) {
175    return new ImmutableMultiset.Builder<E>().add(elements).build();
176  }
177
178  static <E> ImmutableMultiset<E> copyFromEntries(
179      Collection<? extends Entry<? extends E>> entries) {
180    ImmutableMultiset.Builder<E> builder = new ImmutableMultiset.Builder<E>(entries.size());
181    for (Entry<? extends E> entry : entries) {
182      builder.addCopies(entry.getElement(), entry.getCount());
183    }
184    return builder.build();
185  }
186
187  ImmutableMultiset() {}
188
189  @Override
190  public UnmodifiableIterator<E> iterator() {
191    final Iterator<Entry<E>> entryIterator = entrySet().iterator();
192    return new UnmodifiableIterator<E>() {
193      int remaining;
194      @CheckForNull E element;
195
196      @Override
197      public boolean hasNext() {
198        return (remaining > 0) || entryIterator.hasNext();
199      }
200
201      @Override
202      public E next() {
203        if (remaining <= 0) {
204          Entry<E> entry = entryIterator.next();
205          element = entry.getElement();
206          remaining = entry.getCount();
207        }
208        remaining--;
209        /*
210         * requireNonNull is safe because `remaining` starts at 0, forcing us to initialize
211         * `element` above. After that, we never clear it.
212         */
213        return requireNonNull(element);
214      }
215    };
216  }
217
218  @LazyInit @CheckForNull private transient ImmutableList<E> asList;
219
220  @Override
221  public ImmutableList<E> asList() {
222    ImmutableList<E> result = asList;
223    return (result == null) ? asList = super.asList() : result;
224  }
225
226  @Override
227  public boolean contains(@CheckForNull Object object) {
228    return count(object) > 0;
229  }
230
231  /**
232   * Guaranteed to throw an exception and leave the collection unmodified.
233   *
234   * @throws UnsupportedOperationException always
235   * @deprecated Unsupported operation.
236   */
237  @CanIgnoreReturnValue
238  @Deprecated
239  @Override
240  @DoNotCall("Always throws UnsupportedOperationException")
241  public final int add(E element, int occurrences) {
242    throw new UnsupportedOperationException();
243  }
244
245  /**
246   * Guaranteed to throw an exception and leave the collection unmodified.
247   *
248   * @throws UnsupportedOperationException always
249   * @deprecated Unsupported operation.
250   */
251  @CanIgnoreReturnValue
252  @Deprecated
253  @Override
254  @DoNotCall("Always throws UnsupportedOperationException")
255  public final int remove(@CheckForNull Object element, int occurrences) {
256    throw new UnsupportedOperationException();
257  }
258
259  /**
260   * Guaranteed to throw an exception and leave the collection unmodified.
261   *
262   * @throws UnsupportedOperationException always
263   * @deprecated Unsupported operation.
264   */
265  @CanIgnoreReturnValue
266  @Deprecated
267  @Override
268  @DoNotCall("Always throws UnsupportedOperationException")
269  public final int setCount(E element, int count) {
270    throw new UnsupportedOperationException();
271  }
272
273  /**
274   * Guaranteed to throw an exception and leave the collection unmodified.
275   *
276   * @throws UnsupportedOperationException always
277   * @deprecated Unsupported operation.
278   */
279  @CanIgnoreReturnValue
280  @Deprecated
281  @Override
282  @DoNotCall("Always throws UnsupportedOperationException")
283  public final boolean setCount(E element, int oldCount, int newCount) {
284    throw new UnsupportedOperationException();
285  }
286
287  @GwtIncompatible // not present in emulated superclass
288  @Override
289  int copyIntoArray(@Nullable Object[] dst, int offset) {
290    for (Multiset.Entry<E> entry : entrySet()) {
291      Arrays.fill(dst, offset, offset + entry.getCount(), entry.getElement());
292      offset += entry.getCount();
293    }
294    return offset;
295  }
296
297  @Override
298  public boolean equals(@CheckForNull Object object) {
299    return Multisets.equalsImpl(this, object);
300  }
301
302  @Override
303  public int hashCode() {
304    return Sets.hashCodeImpl(entrySet());
305  }
306
307  @Override
308  public String toString() {
309    return entrySet().toString();
310  }
311
312  /** @since 21.0 (present with return type {@code Set} since 2.0) */
313  @Override
314  public abstract ImmutableSet<E> elementSet();
315
316  @LazyInit @CheckForNull private transient ImmutableSet<Entry<E>> entrySet;
317
318  @Override
319  public ImmutableSet<Entry<E>> entrySet() {
320    ImmutableSet<Entry<E>> es = entrySet;
321    return (es == null) ? (entrySet = createEntrySet()) : es;
322  }
323
324  private ImmutableSet<Entry<E>> createEntrySet() {
325    return isEmpty() ? ImmutableSet.<Entry<E>>of() : new EntrySet();
326  }
327
328  abstract Entry<E> getEntry(int index);
329
330  @WeakOuter
331  private final class EntrySet extends IndexedImmutableSet<Entry<E>> {
332    @Override
333    boolean isPartialView() {
334      return ImmutableMultiset.this.isPartialView();
335    }
336
337    @Override
338    Entry<E> get(int index) {
339      return getEntry(index);
340    }
341
342    @Override
343    public int size() {
344      return elementSet().size();
345    }
346
347    @Override
348    public boolean contains(@CheckForNull Object o) {
349      if (o instanceof Entry) {
350        Entry<?> entry = (Entry<?>) o;
351        if (entry.getCount() <= 0) {
352          return false;
353        }
354        int count = count(entry.getElement());
355        return count == entry.getCount();
356      }
357      return false;
358    }
359
360    @Override
361    public int hashCode() {
362      return ImmutableMultiset.this.hashCode();
363    }
364
365    @GwtIncompatible
366    @J2ktIncompatible
367    @Override
368    Object writeReplace() {
369      return new EntrySetSerializedForm<E>(ImmutableMultiset.this);
370    }
371
372    @GwtIncompatible
373    @J2ktIncompatible
374    private void readObject(ObjectInputStream stream) throws InvalidObjectException {
375      throw new InvalidObjectException("Use EntrySetSerializedForm");
376    }
377
378    @J2ktIncompatible private static final long serialVersionUID = 0;
379  }
380
381  @GwtIncompatible
382  @J2ktIncompatible
383  static class EntrySetSerializedForm<E> implements Serializable {
384    final ImmutableMultiset<E> multiset;
385
386    EntrySetSerializedForm(ImmutableMultiset<E> multiset) {
387      this.multiset = multiset;
388    }
389
390    Object readResolve() {
391      return multiset.entrySet();
392    }
393  }
394
395  @GwtIncompatible
396  @J2ktIncompatible
397  @Override
398  abstract Object writeReplace();
399
400  @GwtIncompatible
401  @J2ktIncompatible
402  private void readObject(ObjectInputStream stream) throws InvalidObjectException {
403    throw new InvalidObjectException("Use SerializedForm");
404  }
405
406  /**
407   * Returns a new builder. The generated builder is equivalent to the builder created by the {@link
408   * Builder} constructor.
409   */
410  public static <E> Builder<E> builder() {
411    return new Builder<E>();
412  }
413
414  /**
415   * A builder for creating immutable multiset instances, especially {@code public static final}
416   * multisets ("constant multisets"). Example:
417   *
418   * <pre>{@code
419   * public static final ImmutableMultiset<Bean> BEANS =
420   *     new ImmutableMultiset.Builder<Bean>()
421   *         .addCopies(Bean.COCOA, 4)
422   *         .addCopies(Bean.GARDEN, 6)
423   *         .addCopies(Bean.RED, 8)
424   *         .addCopies(Bean.BLACK_EYED, 10)
425   *         .build();
426   * }</pre>
427   *
428   * <p>Builder instances can be reused; it is safe to call {@link #build} multiple times to build
429   * multiple multisets in series.
430   *
431   * @since 2.0
432   */
433  public static class Builder<E> extends ImmutableCollection.Builder<E> {
434    /*
435     * `contents` is null only for instances of the subclass, ImmutableSortedMultiset.Builder. That
436     * subclass overrides all the methods that access it here. Thus, all the methods here can safely
437     * assume that this field is non-null.
438     */
439    @CheckForNull ObjectCountHashMap<E> contents;
440
441    /**
442     * If build() has been called on the current contents multiset, we need to copy it on any future
443     * modifications, or we'll modify the already-built ImmutableMultiset.
444     */
445    boolean buildInvoked = false;
446    /**
447     * In the event of a setCount(elem, 0) call, we may need to remove elements, which destroys the
448     * insertion order property of ObjectCountHashMap. In that event, we need to convert to a
449     * ObjectCountLinkedHashMap, but we need to know we did that so we can convert back.
450     */
451    boolean isLinkedHash = false;
452
453    /**
454     * Creates a new builder. The returned builder is equivalent to the builder generated by {@link
455     * ImmutableMultiset#builder}.
456     */
457    public Builder() {
458      this(4);
459    }
460
461    Builder(int estimatedDistinct) {
462      this.contents = ObjectCountHashMap.createWithExpectedSize(estimatedDistinct);
463    }
464
465    Builder(boolean forSubtype) {
466      // for ImmutableSortedMultiset not to allocate data structures not used there
467      this.contents = null;
468    }
469
470    /**
471     * Adds {@code element} to the {@code ImmutableMultiset}.
472     *
473     * @param element the element to add
474     * @return this {@code Builder} object
475     * @throws NullPointerException if {@code element} is null
476     */
477    @CanIgnoreReturnValue
478    @Override
479    public Builder<E> add(E element) {
480      return addCopies(element, 1);
481    }
482
483    /**
484     * Adds each element of {@code elements} to the {@code ImmutableMultiset}.
485     *
486     * @param elements the elements to add
487     * @return this {@code Builder} object
488     * @throws NullPointerException if {@code elements} is null or contains a null element
489     */
490    @CanIgnoreReturnValue
491    @Override
492    public Builder<E> add(E... elements) {
493      super.add(elements);
494      return this;
495    }
496
497    /**
498     * Adds a number of occurrences of an element to this {@code ImmutableMultiset}.
499     *
500     * @param element the element to add
501     * @param occurrences the number of occurrences of the element to add. May be zero, in which
502     *     case no change will be made.
503     * @return this {@code Builder} object
504     * @throws NullPointerException if {@code element} is null
505     * @throws IllegalArgumentException if {@code occurrences} is negative, or if this operation
506     *     would result in more than {@link Integer#MAX_VALUE} occurrences of the element
507     */
508    @CanIgnoreReturnValue
509    public Builder<E> addCopies(E element, int occurrences) {
510      requireNonNull(contents); // see the comment on the field
511      if (occurrences == 0) {
512        return this;
513      }
514      if (buildInvoked) {
515        contents = new ObjectCountHashMap<E>(contents);
516        isLinkedHash = false;
517      }
518      buildInvoked = false;
519      checkNotNull(element);
520      contents.put(element, occurrences + contents.get(element));
521      return this;
522    }
523
524    /**
525     * Adds or removes the necessary occurrences of an element such that the element attains the
526     * desired count.
527     *
528     * @param element the element to add or remove occurrences of
529     * @param count the desired count of the element in this multiset
530     * @return this {@code Builder} object
531     * @throws NullPointerException if {@code element} is null
532     * @throws IllegalArgumentException if {@code count} is negative
533     */
534    @CanIgnoreReturnValue
535    public Builder<E> setCount(E element, int count) {
536      requireNonNull(contents); // see the comment on the field
537      if (count == 0 && !isLinkedHash) {
538        contents = new ObjectCountLinkedHashMap<E>(contents);
539        isLinkedHash = true;
540        // to preserve insertion order through deletions, we have to switch to an actual linked
541        // implementation at least for now, but this should be a super rare case
542      } else if (buildInvoked) {
543        contents = new ObjectCountHashMap<E>(contents);
544        isLinkedHash = false;
545      }
546      buildInvoked = false;
547      checkNotNull(element);
548      if (count == 0) {
549        contents.remove(element);
550      } else {
551        contents.put(checkNotNull(element), count);
552      }
553      return this;
554    }
555
556    /**
557     * Adds each element of {@code elements} to the {@code ImmutableMultiset}.
558     *
559     * @param elements the {@code Iterable} to add to the {@code ImmutableMultiset}
560     * @return this {@code Builder} object
561     * @throws NullPointerException if {@code elements} is null or contains a null element
562     */
563    @CanIgnoreReturnValue
564    @Override
565    public Builder<E> addAll(Iterable<? extends E> elements) {
566      requireNonNull(contents); // see the comment on the field
567      if (elements instanceof Multiset) {
568        Multiset<? extends E> multiset = Multisets.cast(elements);
569        ObjectCountHashMap<? extends E> backingMap = tryGetMap(multiset);
570        if (backingMap != null) {
571          contents.ensureCapacity(Math.max(contents.size(), backingMap.size()));
572          for (int i = backingMap.firstIndex(); i >= 0; i = backingMap.nextIndex(i)) {
573            addCopies(backingMap.getKey(i), backingMap.getValue(i));
574          }
575        } else {
576          Set<? extends Entry<? extends E>> entries = multiset.entrySet();
577          contents.ensureCapacity(Math.max(contents.size(), entries.size())); // might overlap
578          for (Entry<? extends E> entry : multiset.entrySet()) {
579            addCopies(entry.getElement(), entry.getCount());
580          }
581        }
582      } else {
583        super.addAll(elements);
584      }
585      return this;
586    }
587
588    /**
589     * Adds each element of {@code elements} to the {@code ImmutableMultiset}.
590     *
591     * @param elements the elements to add to the {@code ImmutableMultiset}
592     * @return this {@code Builder} object
593     * @throws NullPointerException if {@code elements} is null or contains a null element
594     */
595    @CanIgnoreReturnValue
596    @Override
597    public Builder<E> addAll(Iterator<? extends E> elements) {
598      super.addAll(elements);
599      return this;
600    }
601
602    /**
603     * If the specified collection is backed by an ObjectCountHashMap, it will be much more
604     * efficient to iterate over it by index rather than an entry iterator, which will need to
605     * allocate an object for each entry, so we check for that.
606     */
607    @CheckForNull
608    static <T> ObjectCountHashMap<T> tryGetMap(Iterable<T> multiset) {
609      if (multiset instanceof RegularImmutableMultiset) {
610        return ((RegularImmutableMultiset<T>) multiset).contents;
611      } else if (multiset instanceof AbstractMapBasedMultiset) {
612        return ((AbstractMapBasedMultiset<T>) multiset).backingMap;
613      } else {
614        return null;
615      }
616    }
617
618    /**
619     * Returns a newly-created {@code ImmutableMultiset} based on the contents of the {@code
620     * Builder}.
621     */
622    @Override
623    public ImmutableMultiset<E> build() {
624      requireNonNull(contents); // see the comment on the field
625      if (contents.size() == 0) {
626        return of();
627      }
628      if (isLinkedHash) {
629        // we need ObjectCountHashMap-backed contents, with its keys and values array in direct
630        // insertion order
631        contents = new ObjectCountHashMap<E>(contents);
632        isLinkedHash = false;
633      }
634      buildInvoked = true;
635      // contents is now ObjectCountHashMap, but still guaranteed to be in insertion order!
636      return new RegularImmutableMultiset<E>(contents);
637    }
638  }
639}