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
055// TODO(lowasser): write an efficient asList() implementation
056public abstract class ImmutableMultiset<E> extends ImmutableCollection<E> 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}
072   * whose elements are the result of applying {@code elementFunction} to the inputs,
073   * with counts equal to the result of applying {@code countFunction} to the inputs.
074   *
075   * <p>If the mapped elements contain duplicates (according to {@link Object#equals}),
076   * the first occurrence in encounter order appears in the resulting multiset, with count
077   * equal to the sum of the outputs of {@code countFunction.applyAsInt(t)} for each {@code t}
078   * mapped to that element.
079   */
080  private static <T, E> Collector<T, ?, ImmutableMultiset<E>> toImmutableMultiset(
081      Function<? super T, ? extends E> elementFunction, ToIntFunction<? super T> countFunction) {
082    // TODO(lowasser): consider exposing this
083    checkNotNull(elementFunction);
084    checkNotNull(countFunction);
085    return Collector.of(
086        LinkedHashMultiset::create,
087        (multiset, t) -> multiset.add(elementFunction.apply(t), countFunction.applyAsInt(t)),
088        (multiset1, multiset2) -> {
089          multiset1.addAll(multiset2);
090          return multiset1;
091        },
092        (Multiset<E> multiset) -> copyFromEntries(multiset.entrySet()));
093  }
094
095  /**
096   * Returns the empty immutable multiset.
097   */
098  @SuppressWarnings("unchecked") // all supported methods are covariant
099  public static <E> ImmutableMultiset<E> of() {
100    return (ImmutableMultiset<E>) RegularImmutableMultiset.EMPTY;
101  }
102
103  /**
104   * Returns an immutable multiset containing a single element.
105   *
106   * @throws NullPointerException if {@code element} is null
107   * @since 6.0 (source-compatible since 2.0)
108   */
109  @SuppressWarnings("unchecked") // generic array created but never written
110  public static <E> ImmutableMultiset<E> of(E element) {
111    return copyFromElements(element);
112  }
113
114  /**
115   * Returns an immutable multiset containing the given elements, in order.
116   *
117   * @throws NullPointerException if any element is null
118   * @since 6.0 (source-compatible since 2.0)
119   */
120  @SuppressWarnings("unchecked") //
121  public static <E> ImmutableMultiset<E> of(E e1, E e2) {
122    return copyFromElements(e1, e2);
123  }
124
125  /**
126   * Returns an immutable multiset containing the given elements, in the "grouped iteration order"
127   * described in the class documentation.
128   *
129   * @throws NullPointerException if any element is null
130   * @since 6.0 (source-compatible since 2.0)
131   */
132  @SuppressWarnings("unchecked") //
133  public static <E> ImmutableMultiset<E> of(E e1, E e2, E e3) {
134    return copyFromElements(e1, e2, e3);
135  }
136
137  /**
138   * Returns an immutable multiset containing the given elements, in the "grouped iteration order"
139   * described in the class documentation.
140   *
141   * @throws NullPointerException if any element is null
142   * @since 6.0 (source-compatible since 2.0)
143   */
144  @SuppressWarnings("unchecked") //
145  public static <E> ImmutableMultiset<E> of(E e1, E e2, E e3, E e4) {
146    return copyFromElements(e1, e2, e3, e4);
147  }
148
149  /**
150   * Returns an immutable multiset containing the given elements, in the "grouped iteration order"
151   * described in the class documentation.
152   *
153   * @throws NullPointerException if any element is null
154   * @since 6.0 (source-compatible since 2.0)
155   */
156  @SuppressWarnings("unchecked") //
157  public static <E> ImmutableMultiset<E> of(E e1, E e2, E e3, E e4, E e5) {
158    return copyFromElements(e1, e2, e3, e4, e5);
159  }
160
161  /**
162   * Returns an immutable multiset containing the given elements, in the "grouped iteration order"
163   * described in the class documentation.
164   *
165   * @throws NullPointerException if any element is null
166   * @since 6.0 (source-compatible since 2.0)
167   */
168  @SuppressWarnings("unchecked") //
169  public static <E> ImmutableMultiset<E> of(E e1, E e2, E e3, E e4, E e5, E e6, E... others) {
170    return new Builder<E>().add(e1).add(e2).add(e3).add(e4).add(e5).add(e6).add(others).build();
171  }
172
173  /**
174   * Returns an immutable multiset containing the given elements, in the "grouped iteration order"
175   * described in the class documentation.
176   *
177   * @throws NullPointerException if any of {@code elements} is null
178   * @since 6.0
179   */
180  public static <E> ImmutableMultiset<E> copyOf(E[] elements) {
181    return copyFromElements(elements);
182  }
183
184  /**
185   * Returns an immutable multiset containing the given elements, in the "grouped iteration order"
186   * described in the class documentation.
187   *
188   * @throws NullPointerException if any of {@code elements} is null
189   */
190  public static <E> ImmutableMultiset<E> copyOf(Iterable<? extends E> elements) {
191    if (elements instanceof ImmutableMultiset) {
192      @SuppressWarnings("unchecked") // all supported methods are covariant
193      ImmutableMultiset<E> result = (ImmutableMultiset<E>) elements;
194      if (!result.isPartialView()) {
195        return result;
196      }
197    }
198
199    Multiset<? extends E> multiset =
200        (elements instanceof Multiset)
201            ? Multisets.cast(elements)
202            : LinkedHashMultiset.create(elements);
203
204    return copyFromEntries(multiset.entrySet());
205  }
206
207  private static <E> ImmutableMultiset<E> copyFromElements(E... elements) {
208    Multiset<E> multiset = LinkedHashMultiset.create();
209    Collections.addAll(multiset, elements);
210    return copyFromEntries(multiset.entrySet());
211  }
212
213  static <E> ImmutableMultiset<E> copyFromEntries(
214      Collection<? extends Entry<? extends E>> entries) {
215    if (entries.isEmpty()) {
216      return of();
217    } else {
218      return new RegularImmutableMultiset<E>(entries);
219    }
220  }
221
222  /**
223   * Returns an immutable multiset containing the given elements, in the "grouped iteration order"
224   * described in the class documentation.
225   *
226   * @throws NullPointerException if any of {@code elements} is null
227   */
228  public static <E> ImmutableMultiset<E> copyOf(Iterator<? extends E> elements) {
229    Multiset<E> multiset = LinkedHashMultiset.create();
230    Iterators.addAll(multiset, elements);
231    return copyFromEntries(multiset.entrySet());
232  }
233
234  ImmutableMultiset() {}
235
236  @Override
237  public UnmodifiableIterator<E> iterator() {
238    final Iterator<Entry<E>> entryIterator = entrySet().iterator();
239    return new UnmodifiableIterator<E>() {
240      int remaining;
241      E element;
242
243      @Override
244      public boolean hasNext() {
245        return (remaining > 0) || entryIterator.hasNext();
246      }
247
248      @Override
249      public E next() {
250        if (remaining <= 0) {
251          Entry<E> entry = entryIterator.next();
252          element = entry.getElement();
253          remaining = entry.getCount();
254        }
255        remaining--;
256        return element;
257      }
258    };
259  }
260
261  @LazyInit
262  private transient ImmutableList<E> asList;
263
264  @Override
265  public ImmutableList<E> asList() {
266    ImmutableList<E> result = asList;
267    return (result == null) ? asList = createAsList() : result;
268  }
269
270  ImmutableList<E> createAsList() {
271    if (isEmpty()) {
272      return ImmutableList.of();
273    }
274    return new RegularImmutableAsList<E>(this, toArray());
275  }
276
277  @Override
278  public boolean contains(@Nullable Object object) {
279    return count(object) > 0;
280  }
281
282  /**
283   * Guaranteed to throw an exception and leave the collection unmodified.
284   *
285   * @throws UnsupportedOperationException always
286   * @deprecated Unsupported operation.
287   */
288  @CanIgnoreReturnValue
289  @Deprecated
290  @Override
291  public final int add(E element, int occurrences) {
292    throw new UnsupportedOperationException();
293  }
294
295  /**
296   * Guaranteed to throw an exception and leave the collection unmodified.
297   *
298   * @throws UnsupportedOperationException always
299   * @deprecated Unsupported operation.
300   */
301  @CanIgnoreReturnValue
302  @Deprecated
303  @Override
304  public final int remove(Object element, int occurrences) {
305    throw new UnsupportedOperationException();
306  }
307
308  /**
309   * Guaranteed to throw an exception and leave the collection unmodified.
310   *
311   * @throws UnsupportedOperationException always
312   * @deprecated Unsupported operation.
313   */
314  @CanIgnoreReturnValue
315  @Deprecated
316  @Override
317  public final int setCount(E element, int count) {
318    throw new UnsupportedOperationException();
319  }
320
321  /**
322   * Guaranteed to throw an exception and leave the collection unmodified.
323   *
324   * @throws UnsupportedOperationException always
325   * @deprecated Unsupported operation.
326   */
327  @CanIgnoreReturnValue
328  @Deprecated
329  @Override
330  public final boolean setCount(E element, int oldCount, int newCount) {
331    throw new UnsupportedOperationException();
332  }
333
334  @GwtIncompatible // not present in emulated superclass
335  @Override
336  int copyIntoArray(Object[] dst, int offset) {
337    for (Multiset.Entry<E> entry : entrySet()) {
338      Arrays.fill(dst, offset, offset + entry.getCount(), entry.getElement());
339      offset += entry.getCount();
340    }
341    return offset;
342  }
343
344  @Override
345  public boolean equals(@Nullable Object object) {
346    return Multisets.equalsImpl(this, object);
347  }
348
349  @Override
350  public int hashCode() {
351    return Sets.hashCodeImpl(entrySet());
352  }
353
354  @Override
355  public String toString() {
356    return entrySet().toString();
357  }
358
359  /** @since 21.0 (present with return type {@code Set} since 2.0) */
360  @Override
361  public abstract ImmutableSet<E> elementSet();
362
363  @LazyInit
364  private transient ImmutableSet<Entry<E>> entrySet;
365
366  @Override
367  public ImmutableSet<Entry<E>> entrySet() {
368    ImmutableSet<Entry<E>> es = entrySet;
369    return (es == null) ? (entrySet = createEntrySet()) : es;
370  }
371
372  private final ImmutableSet<Entry<E>> createEntrySet() {
373    return isEmpty() ? ImmutableSet.<Entry<E>>of() : new EntrySet();
374  }
375
376  abstract Entry<E> getEntry(int index);
377
378  @WeakOuter
379  private final class EntrySet extends ImmutableSet.Indexed<Entry<E>> {
380    @Override
381    boolean isPartialView() {
382      return ImmutableMultiset.this.isPartialView();
383    }
384
385    @Override
386    Entry<E> get(int index) {
387      return getEntry(index);
388    }
389
390    @Override
391    public int size() {
392      return elementSet().size();
393    }
394
395    @Override
396    public boolean contains(Object o) {
397      if (o instanceof Entry) {
398        Entry<?> entry = (Entry<?>) o;
399        if (entry.getCount() <= 0) {
400          return false;
401        }
402        int count = count(entry.getElement());
403        return count == entry.getCount();
404      }
405      return false;
406    }
407
408    @Override
409    public int hashCode() {
410      return ImmutableMultiset.this.hashCode();
411    }
412
413    // We can't label this with @Override, because it doesn't override anything
414    // in the GWT emulated version.
415    // TODO(cpovirk): try making all copies of this method @GwtIncompatible instead
416    Object writeReplace() {
417      return new EntrySetSerializedForm<E>(ImmutableMultiset.this);
418    }
419
420    private static final long serialVersionUID = 0;
421  }
422
423  static class EntrySetSerializedForm<E> implements Serializable {
424    final ImmutableMultiset<E> multiset;
425
426    EntrySetSerializedForm(ImmutableMultiset<E> multiset) {
427      this.multiset = multiset;
428    }
429
430    Object readResolve() {
431      return multiset.entrySet();
432    }
433  }
434
435  private static class SerializedForm implements Serializable {
436    final Object[] elements;
437    final int[] counts;
438
439    SerializedForm(Multiset<?> multiset) {
440      int distinct = multiset.entrySet().size();
441      elements = new Object[distinct];
442      counts = new int[distinct];
443      int i = 0;
444      for (Entry<?> entry : multiset.entrySet()) {
445        elements[i] = entry.getElement();
446        counts[i] = entry.getCount();
447        i++;
448      }
449    }
450
451    Object readResolve() {
452      LinkedHashMultiset<Object> multiset = LinkedHashMultiset.create(elements.length);
453      for (int i = 0; i < elements.length; i++) {
454        multiset.add(elements[i], counts[i]);
455      }
456      return ImmutableMultiset.copyOf(multiset);
457    }
458
459    private static final long serialVersionUID = 0;
460  }
461
462  // We can't label this with @Override, because it doesn't override anything
463  // in the GWT emulated version.
464  Object writeReplace() {
465    return new SerializedForm(this);
466  }
467
468  /**
469   * Returns a new builder. The generated builder is equivalent to the builder
470   * created by the {@link Builder} constructor.
471   */
472  public static <E> Builder<E> builder() {
473    return new Builder<E>();
474  }
475
476  /**
477   * A builder for creating immutable multiset instances, especially {@code
478   * public static final} multisets ("constant multisets"). Example:
479   * <pre> {@code
480   *
481   *   public static final ImmutableMultiset<Bean> BEANS =
482   *       new ImmutableMultiset.Builder<Bean>()
483   *           .addCopies(Bean.COCOA, 4)
484   *           .addCopies(Bean.GARDEN, 6)
485   *           .addCopies(Bean.RED, 8)
486   *           .addCopies(Bean.BLACK_EYED, 10)
487   *           .build();}</pre>
488   *
489   * <p>Builder instances can be reused; it is safe to call {@link #build} multiple
490   * times to build multiple multisets in series.
491   *
492   * @since 2.0
493   */
494  public static class Builder<E> extends ImmutableCollection.Builder<E> {
495    final Multiset<E> contents;
496
497    /**
498     * Creates a new builder. The returned builder is equivalent to the builder
499     * generated by {@link ImmutableMultiset#builder}.
500     */
501    public Builder() {
502      this(LinkedHashMultiset.<E>create());
503    }
504
505    Builder(Multiset<E> contents) {
506      this.contents = contents;
507    }
508
509    /**
510     * Adds {@code element} to the {@code ImmutableMultiset}.
511     *
512     * @param element the element to add
513     * @return this {@code Builder} object
514     * @throws NullPointerException if {@code element} is null
515     */
516    @CanIgnoreReturnValue
517    @Override
518    public Builder<E> add(E element) {
519      contents.add(checkNotNull(element));
520      return this;
521    }
522
523    /**
524     * Adds a number of occurrences of an element to this {@code
525     * ImmutableMultiset}.
526     *
527     * @param element the element to add
528     * @param occurrences the number of occurrences of the element to add. May
529     *     be zero, in which case no change will be made.
530     * @return this {@code Builder} object
531     * @throws NullPointerException if {@code element} is null
532     * @throws IllegalArgumentException if {@code occurrences} is negative, or
533     *     if this operation would result in more than {@link Integer#MAX_VALUE}
534     *     occurrences of the element
535     */
536    @CanIgnoreReturnValue
537    public Builder<E> addCopies(E element, int occurrences) {
538      contents.add(checkNotNull(element), occurrences);
539      return this;
540    }
541
542    /**
543     * Adds or removes the necessary occurrences of an element such that the
544     * element attains the desired count.
545     *
546     * @param element the element to add or remove occurrences of
547     * @param count the desired count of the element in this multiset
548     * @return this {@code Builder} object
549     * @throws NullPointerException if {@code element} is null
550     * @throws IllegalArgumentException if {@code count} is negative
551     */
552    @CanIgnoreReturnValue
553    public Builder<E> setCount(E element, int count) {
554      contents.setCount(checkNotNull(element), count);
555      return this;
556    }
557
558    /**
559     * Adds each element of {@code elements} to the {@code ImmutableMultiset}.
560     *
561     * @param elements the elements to add
562     * @return this {@code Builder} object
563     * @throws NullPointerException if {@code elements} is null or contains a
564     *     null element
565     */
566    @CanIgnoreReturnValue
567    @Override
568    public Builder<E> add(E... elements) {
569      super.add(elements);
570      return this;
571    }
572
573    /**
574     * Adds each element of {@code elements} to the {@code ImmutableMultiset}.
575     *
576     * @param elements the {@code Iterable} to add to the {@code
577     *     ImmutableMultiset}
578     * @return this {@code Builder} object
579     * @throws NullPointerException if {@code elements} is null or contains a
580     *     null element
581     */
582    @CanIgnoreReturnValue
583    @Override
584    public Builder<E> addAll(Iterable<? extends E> elements) {
585      if (elements instanceof Multiset) {
586        Multiset<? extends E> multiset = Multisets.cast(elements);
587        for (Entry<? extends E> entry : multiset.entrySet()) {
588          addCopies(entry.getElement(), entry.getCount());
589        }
590      } else {
591        super.addAll(elements);
592      }
593      return this;
594    }
595
596    /**
597     * Adds each element of {@code elements} to the {@code ImmutableMultiset}.
598     *
599     * @param elements the elements to add to the {@code ImmutableMultiset}
600     * @return this {@code Builder} object
601     * @throws NullPointerException if {@code elements} is null or contains a
602     *     null element
603     */
604    @CanIgnoreReturnValue
605    @Override
606    public Builder<E> addAll(Iterator<? extends E> elements) {
607      super.addAll(elements);
608      return this;
609    }
610
611    /**
612     * Returns a newly-created {@code ImmutableMultiset} based on the contents
613     * of the {@code Builder}.
614     */
615    @Override
616    public ImmutableMultiset<E> build() {
617      return copyOf(contents);
618    }
619  }
620}