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.j2objc.annotations.WeakOuter;
025
026import java.io.Serializable;
027import java.util.Arrays;
028import java.util.Collection;
029import java.util.Collections;
030import java.util.Iterator;
031
032import javax.annotation.Nullable;
033
034/**
035 * A {@link Multiset} whose contents will never change, with many other important properties
036 * detailed at {@link ImmutableCollection}.
037 *
038 * <p><b>Grouped iteration.</b> In all current implementations, duplicate elements always appear
039 * consecutively when iterating. Elements iterate in order by the <i>first</i> appearance of
040 * that element when the multiset was created.
041 *
042 * <p>See the Guava User Guide article on <a href=
043 * "https://github.com/google/guava/wiki/ImmutableCollectionsExplained">
044 * 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// TODO(lowasser): write an efficient asList() implementation
053public abstract class ImmutableMultiset<E> extends ImmutableCollection<E> implements Multiset<E> {
054  /**
055   * Returns the empty immutable multiset.
056   */
057  @SuppressWarnings("unchecked") // all supported methods are covariant
058  public static <E> ImmutableMultiset<E> of() {
059    return (ImmutableMultiset<E>) RegularImmutableMultiset.EMPTY;
060  }
061
062  /**
063   * Returns an immutable multiset containing a single element.
064   *
065   * @throws NullPointerException if {@code element} is null
066   * @since 6.0 (source-compatible since 2.0)
067   */
068  @SuppressWarnings("unchecked") // generic array created but never written
069  public static <E> ImmutableMultiset<E> of(E element) {
070    return copyFromElements(element);
071  }
072
073  /**
074   * Returns an immutable multiset containing the given elements, in order.
075   *
076   * @throws NullPointerException if any element is null
077   * @since 6.0 (source-compatible since 2.0)
078   */
079  @SuppressWarnings("unchecked") //
080  public static <E> ImmutableMultiset<E> of(E e1, E e2) {
081    return copyFromElements(e1, e2);
082  }
083
084  /**
085   * Returns an immutable multiset containing the given elements, in the "grouped iteration order"
086   * described in the class documentation.
087   *
088   * @throws NullPointerException if any element is null
089   * @since 6.0 (source-compatible since 2.0)
090   */
091  @SuppressWarnings("unchecked") //
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  @SuppressWarnings("unchecked") //
104  public static <E> ImmutableMultiset<E> of(E e1, E e2, E e3, E e4) {
105    return copyFromElements(e1, e2, e3, e4);
106  }
107
108  /**
109   * Returns an immutable multiset containing the given elements, in the "grouped iteration order"
110   * described in the class documentation.
111   *
112   * @throws NullPointerException if any element is null
113   * @since 6.0 (source-compatible since 2.0)
114   */
115  @SuppressWarnings("unchecked") //
116  public static <E> ImmutableMultiset<E> of(E e1, E e2, E e3, E e4, E e5) {
117    return copyFromElements(e1, e2, e3, e4, e5);
118  }
119
120  /**
121   * Returns an immutable multiset containing the given elements, in the "grouped iteration order"
122   * described in the class documentation.
123   *
124   * @throws NullPointerException if any element is null
125   * @since 6.0 (source-compatible since 2.0)
126   */
127  @SuppressWarnings("unchecked") //
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>()
130        .add(e1)
131        .add(e2)
132        .add(e3)
133        .add(e4)
134        .add(e5)
135        .add(e6)
136        .add(others)
137        .build();
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   * @since 6.0
146   */
147  public static <E> ImmutableMultiset<E> copyOf(E[] elements) {
148    return copyFromElements(elements);
149  }
150
151  /**
152   * Returns an immutable multiset containing the given elements, in the "grouped iteration order"
153   * described in the class documentation.
154   *
155   * @throws NullPointerException if any of {@code elements} is null
156   */
157  public static <E> ImmutableMultiset<E> copyOf(Iterable<? extends E> elements) {
158    if (elements instanceof ImmutableMultiset) {
159      @SuppressWarnings("unchecked") // all supported methods are covariant
160      ImmutableMultiset<E> result = (ImmutableMultiset<E>) elements;
161      if (!result.isPartialView()) {
162        return result;
163      }
164    }
165
166    Multiset<? extends E> multiset =
167        (elements instanceof Multiset)
168            ? Multisets.cast(elements)
169            : LinkedHashMultiset.create(elements);
170
171    return copyFromEntries(multiset.entrySet());
172  }
173
174  private static <E> ImmutableMultiset<E> copyFromElements(E... elements) {
175    Multiset<E> multiset = LinkedHashMultiset.create();
176    Collections.addAll(multiset, elements);
177    return copyFromEntries(multiset.entrySet());
178  }
179
180  static <E> ImmutableMultiset<E> copyFromEntries(
181      Collection<? extends Entry<? extends E>> entries) {
182    if (entries.isEmpty()) {
183      return of();
184    } else {
185      return new RegularImmutableMultiset<E>(entries);
186    }
187  }
188
189  /**
190   * Returns an immutable multiset containing the given elements, in the "grouped iteration order"
191   * described in the class documentation.
192   *
193   * @throws NullPointerException if any of {@code elements} is null
194   */
195  public static <E> ImmutableMultiset<E> copyOf(Iterator<? extends E> elements) {
196    Multiset<E> multiset = LinkedHashMultiset.create();
197    Iterators.addAll(multiset, elements);
198    return copyFromEntries(multiset.entrySet());
199  }
200
201  ImmutableMultiset() {}
202
203  @Override
204  public UnmodifiableIterator<E> iterator() {
205    final Iterator<Entry<E>> entryIterator = entrySet().iterator();
206    return new UnmodifiableIterator<E>() {
207      int remaining;
208      E element;
209
210      @Override
211      public boolean hasNext() {
212        return (remaining > 0) || entryIterator.hasNext();
213      }
214
215      @Override
216      public E next() {
217        if (remaining <= 0) {
218          Entry<E> entry = entryIterator.next();
219          element = entry.getElement();
220          remaining = entry.getCount();
221        }
222        remaining--;
223        return element;
224      }
225    };
226  }
227
228  @Override
229  public boolean contains(@Nullable Object object) {
230    return count(object) > 0;
231  }
232
233  /**
234   * Guaranteed to throw an exception and leave the collection unmodified.
235   *
236   * @throws UnsupportedOperationException always
237   * @deprecated Unsupported operation.
238   */
239  @Deprecated
240  @Override
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  @Deprecated
252  @Override
253  public final int remove(Object element, int occurrences) {
254    throw new UnsupportedOperationException();
255  }
256
257  /**
258   * Guaranteed to throw an exception and leave the collection unmodified.
259   *
260   * @throws UnsupportedOperationException always
261   * @deprecated Unsupported operation.
262   */
263  @Deprecated
264  @Override
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  @Deprecated
276  @Override
277  public final boolean setCount(E element, int oldCount, int newCount) {
278    throw new UnsupportedOperationException();
279  }
280
281  @GwtIncompatible("not present in emulated superclass")
282  @Override
283  int copyIntoArray(Object[] dst, int offset) {
284    for (Multiset.Entry<E> entry : entrySet()) {
285      Arrays.fill(dst, offset, offset + entry.getCount(), entry.getElement());
286      offset += entry.getCount();
287    }
288    return offset;
289  }
290
291  @Override
292  public boolean equals(@Nullable Object object) {
293    return Multisets.equalsImpl(this, object);
294  }
295
296  @Override
297  public int hashCode() {
298    return Sets.hashCodeImpl(entrySet());
299  }
300
301  @Override
302  public String toString() {
303    return entrySet().toString();
304  }
305
306  private transient ImmutableSet<Entry<E>> entrySet;
307
308  @Override
309  public ImmutableSet<Entry<E>> entrySet() {
310    ImmutableSet<Entry<E>> es = entrySet;
311    return (es == null) ? (entrySet = createEntrySet()) : es;
312  }
313
314  private final ImmutableSet<Entry<E>> createEntrySet() {
315    return isEmpty() ? ImmutableSet.<Entry<E>>of() : new EntrySet();
316  }
317
318  abstract Entry<E> getEntry(int index);
319
320  @WeakOuter
321  private final class EntrySet extends ImmutableSet.Indexed<Entry<E>> {
322    @Override
323    boolean isPartialView() {
324      return ImmutableMultiset.this.isPartialView();
325    }
326
327    @Override
328    Entry<E> get(int index) {
329      return getEntry(index);
330    }
331
332    @Override
333    public int size() {
334      return elementSet().size();
335    }
336
337    @Override
338    public boolean contains(Object o) {
339      if (o instanceof Entry) {
340        Entry<?> entry = (Entry<?>) o;
341        if (entry.getCount() <= 0) {
342          return false;
343        }
344        int count = count(entry.getElement());
345        return count == entry.getCount();
346      }
347      return false;
348    }
349
350    @Override
351    public int hashCode() {
352      return ImmutableMultiset.this.hashCode();
353    }
354
355    // We can't label this with @Override, because it doesn't override anything
356    // in the GWT emulated version.
357    // TODO(cpovirk): try making all copies of this method @GwtIncompatible instead
358    Object writeReplace() {
359      return new EntrySetSerializedForm<E>(ImmutableMultiset.this);
360    }
361
362    private static final long serialVersionUID = 0;
363  }
364
365  static class EntrySetSerializedForm<E> implements Serializable {
366    final ImmutableMultiset<E> multiset;
367
368    EntrySetSerializedForm(ImmutableMultiset<E> multiset) {
369      this.multiset = multiset;
370    }
371
372    Object readResolve() {
373      return multiset.entrySet();
374    }
375  }
376
377  private static class SerializedForm implements Serializable {
378    final Object[] elements;
379    final int[] counts;
380
381    SerializedForm(Multiset<?> multiset) {
382      int distinct = multiset.entrySet().size();
383      elements = new Object[distinct];
384      counts = new int[distinct];
385      int i = 0;
386      for (Entry<?> entry : multiset.entrySet()) {
387        elements[i] = entry.getElement();
388        counts[i] = entry.getCount();
389        i++;
390      }
391    }
392
393    Object readResolve() {
394      LinkedHashMultiset<Object> multiset = LinkedHashMultiset.create(elements.length);
395      for (int i = 0; i < elements.length; i++) {
396        multiset.add(elements[i], counts[i]);
397      }
398      return ImmutableMultiset.copyOf(multiset);
399    }
400
401    private static final long serialVersionUID = 0;
402  }
403
404  // We can't label this with @Override, because it doesn't override anything
405  // in the GWT emulated version.
406  Object writeReplace() {
407    return new SerializedForm(this);
408  }
409
410  /**
411   * Returns a new builder. The generated builder is equivalent to the builder
412   * created by the {@link Builder} constructor.
413   */
414  public static <E> Builder<E> builder() {
415    return new Builder<E>();
416  }
417
418  /**
419   * A builder for creating immutable multiset instances, especially {@code
420   * public static final} multisets ("constant multisets"). Example:
421   * <pre> {@code
422   *
423   *   public static final ImmutableMultiset<Bean> BEANS =
424   *       new ImmutableMultiset.Builder<Bean>()
425   *           .addCopies(Bean.COCOA, 4)
426   *           .addCopies(Bean.GARDEN, 6)
427   *           .addCopies(Bean.RED, 8)
428   *           .addCopies(Bean.BLACK_EYED, 10)
429   *           .build();}</pre>
430   *
431   * <p>Builder instances can be reused; it is safe to call {@link #build} multiple
432   * times to build multiple multisets in series.
433   *
434   * @since 2.0
435   */
436  public static class Builder<E> extends ImmutableCollection.Builder<E> {
437    final Multiset<E> contents;
438
439    /**
440     * Creates a new builder. The returned builder is equivalent to the builder
441     * generated by {@link ImmutableMultiset#builder}.
442     */
443    public Builder() {
444      this(LinkedHashMultiset.<E>create());
445    }
446
447    Builder(Multiset<E> contents) {
448      this.contents = contents;
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    @Override
459    public Builder<E> add(E element) {
460      contents.add(checkNotNull(element));
461      return this;
462    }
463
464    /**
465     * Adds a number of occurrences of an element to this {@code
466     * ImmutableMultiset}.
467     *
468     * @param element the element to add
469     * @param occurrences the number of occurrences of the element to add. May
470     *     be zero, in which case no change will be made.
471     * @return this {@code Builder} object
472     * @throws NullPointerException if {@code element} is null
473     * @throws IllegalArgumentException if {@code occurrences} is negative, or
474     *     if this operation would result in more than {@link Integer#MAX_VALUE}
475     *     occurrences of the element
476     */
477    public Builder<E> addCopies(E element, int occurrences) {
478      contents.add(checkNotNull(element), occurrences);
479      return this;
480    }
481
482    /**
483     * Adds or removes the necessary occurrences of an element such that the
484     * element attains the desired count.
485     *
486     * @param element the element to add or remove occurrences of
487     * @param count the desired count of the element in this multiset
488     * @return this {@code Builder} object
489     * @throws NullPointerException if {@code element} is null
490     * @throws IllegalArgumentException if {@code count} is negative
491     */
492    public Builder<E> setCount(E element, int count) {
493      contents.setCount(checkNotNull(element), count);
494      return this;
495    }
496
497    /**
498     * Adds each element of {@code elements} to the {@code ImmutableMultiset}.
499     *
500     * @param elements the elements to add
501     * @return this {@code Builder} object
502     * @throws NullPointerException if {@code elements} is null or contains a
503     *     null element
504     */
505    @Override
506    public Builder<E> add(E... elements) {
507      super.add(elements);
508      return this;
509    }
510
511    /**
512     * Adds each element of {@code elements} to the {@code ImmutableMultiset}.
513     *
514     * @param elements the {@code Iterable} to add to the {@code
515     *     ImmutableMultiset}
516     * @return this {@code Builder} object
517     * @throws NullPointerException if {@code elements} is null or contains a
518     *     null element
519     */
520    @Override
521    public Builder<E> addAll(Iterable<? extends E> elements) {
522      if (elements instanceof Multiset) {
523        Multiset<? extends E> multiset = Multisets.cast(elements);
524        for (Entry<? extends E> entry : multiset.entrySet()) {
525          addCopies(entry.getElement(), entry.getCount());
526        }
527      } else {
528        super.addAll(elements);
529      }
530      return this;
531    }
532
533    /**
534     * Adds each element of {@code elements} to the {@code ImmutableMultiset}.
535     *
536     * @param elements the elements to add to the {@code ImmutableMultiset}
537     * @return this {@code Builder} object
538     * @throws NullPointerException if {@code elements} is null or contains a
539     *     null element
540     */
541    @Override
542    public Builder<E> addAll(Iterator<? extends E> elements) {
543      super.addAll(elements);
544      return this;
545    }
546
547    /**
548     * Returns a newly-created {@code ImmutableMultiset} based on the contents
549     * of the {@code Builder}.
550     */
551    @Override
552    public ImmutableMultiset<E> build() {
553      return copyOf(contents);
554    }
555  }
556}