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