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