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