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.common.primitives.Ints;
025
026import java.io.Serializable;
027import java.util.Arrays;
028import java.util.Collection;
029import java.util.Iterator;
030
031import javax.annotation.Nullable;
032
033/**
034 * An immutable hash-based multiset. Does not permit null elements.
035 *
036 * <p>Its iterator orders elements according to the first appearance of the
037 * element among the items passed to the factory method or builder. When the
038 * multiset contains multiple instances of an element, those instances are
039 * consecutive in the iteration order.
040 *
041 * <p>See the Guava User Guide article on <a href=
042 * "http://code.google.com/p/guava-libraries/wiki/ImmutableCollectionsExplained">
043 * immutable collections</a>.
044 *
045 * @author Jared Levy
046 * @author Louis Wasserman
047 * @since 2.0 (imported from Google Collections Library)
048 */
049@GwtCompatible(serializable = true, emulated = true)
050@SuppressWarnings("serial") // we're overriding default serialization
051// TODO(user): write an efficient asList() implementation
052public abstract class ImmutableMultiset<E> extends ImmutableCollection<E>
053    implements Multiset<E> {
054
055  private static final ImmutableMultiset<Object> EMPTY =
056      new RegularImmutableMultiset<Object>(ImmutableMap.<Object, Integer>of(), 0);
057
058  /**
059   * Returns the empty immutable multiset.
060   */
061  @SuppressWarnings("unchecked") // all supported methods are covariant
062  public static <E> ImmutableMultiset<E> of() {
063    return (ImmutableMultiset<E>) EMPTY;
064  }
065
066  /**
067   * Returns an immutable multiset containing a single element.
068   *
069   * @throws NullPointerException if {@code element} is null
070   * @since 6.0 (source-compatible since 2.0)
071   */
072  @SuppressWarnings("unchecked") // generic array created but never written
073  public static <E> ImmutableMultiset<E> of(E element) {
074    return copyOfInternal(element);
075  }
076
077  /**
078   * Returns an immutable multiset containing the given elements, in order.
079   *
080   * @throws NullPointerException if any element is null
081   * @since 6.0 (source-compatible since 2.0)
082   */
083  @SuppressWarnings("unchecked") //
084  public static <E> ImmutableMultiset<E> of(E e1, E e2) {
085    return copyOfInternal(e1, e2);
086  }
087
088  /**
089   * Returns an immutable multiset containing the given elements, in order.
090   *
091   * @throws NullPointerException if any element is null
092   * @since 6.0 (source-compatible since 2.0)
093   */
094  @SuppressWarnings("unchecked") //
095  public static <E> ImmutableMultiset<E> of(E e1, E e2, E e3) {
096    return copyOfInternal(e1, e2, e3);
097  }
098
099  /**
100   * Returns an immutable multiset containing the given elements, in order.
101   *
102   * @throws NullPointerException if any element is null
103   * @since 6.0 (source-compatible since 2.0)
104   */
105  @SuppressWarnings("unchecked") //
106  public static <E> ImmutableMultiset<E> of(E e1, E e2, E e3, E e4) {
107    return copyOfInternal(e1, e2, e3, e4);
108  }
109
110  /**
111   * Returns an immutable multiset containing the given elements, in order.
112   *
113   * @throws NullPointerException if any element is null
114   * @since 6.0 (source-compatible since 2.0)
115   */
116  @SuppressWarnings("unchecked") //
117  public static <E> ImmutableMultiset<E> of(E e1, E e2, E e3, E e4, E e5) {
118    return copyOfInternal(e1, e2, e3, e4, e5);
119  }
120
121  /**
122   * Returns an immutable multiset containing the given elements, in order.
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(
129      E e1, E e2, E e3, E e4, E e5, E e6, E... others) {
130    return new Builder<E>()
131        .add(e1)
132        .add(e2)
133        .add(e3)
134        .add(e4)
135        .add(e5)
136        .add(e6)
137        .add(others)
138        .build();
139  }
140
141  /**
142   * Returns an immutable multiset containing the given elements.
143   *
144   * <p>The multiset is ordered by the first occurrence of each element. For
145   * example, {@code ImmutableMultiset.copyOf([2, 3, 1, 3])} yields a multiset
146   * with elements in the order {@code 2, 3, 3, 1}.
147   *
148   * @throws NullPointerException if any of {@code elements} is null
149   * @since 6.0
150   */
151  public static <E> ImmutableMultiset<E> copyOf(E[] elements) {
152    return copyOf(Arrays.asList(elements));
153  }
154
155  /**
156   * Returns an immutable multiset containing the given elements.
157   *
158   * <p>The multiset is ordered by the first occurrence of each element. For
159   * example, {@code ImmutableMultiset.copyOf(Arrays.asList(2, 3, 1, 3))} yields
160   * a multiset with elements in the order {@code 2, 3, 3, 1}.
161   *
162   * <p>Despite the method name, this method attempts to avoid actually copying
163   * the data when it is safe to do so. The exact circumstances under which a
164   * copy will or will not be performed are undocumented and subject to change.
165   *
166   * <p><b>Note:</b> Despite what the method name suggests, if {@code elements}
167   * is an {@code ImmutableMultiset}, no copy will actually be performed, and
168   * the given multiset itself will be returned.
169   *
170   * @throws NullPointerException if any of {@code elements} is null
171   */
172  public static <E> ImmutableMultiset<E> copyOf(
173      Iterable<? extends E> elements) {
174    if (elements instanceof ImmutableMultiset) {
175      @SuppressWarnings("unchecked") // all supported methods are covariant
176      ImmutableMultiset<E> result = (ImmutableMultiset<E>) elements;
177      if (!result.isPartialView()) {
178        return result;
179      }
180    }
181
182    Multiset<? extends E> multiset = (elements instanceof Multiset)
183        ? Multisets.cast(elements)
184        : LinkedHashMultiset.create(elements);
185
186    return copyOfInternal(multiset);
187  }
188
189  private static <E> ImmutableMultiset<E> copyOfInternal(E... elements) {
190    return copyOf(Arrays.asList(elements));
191  }
192
193  private static <E> ImmutableMultiset<E> copyOfInternal(
194      Multiset<? extends E> multiset) {
195    return copyFromEntries(multiset.entrySet());
196  }
197
198  static <E> ImmutableMultiset<E> copyFromEntries(
199      Collection<? extends Entry<? extends E>> entries) {
200    long size = 0;
201    ImmutableMap.Builder<E, Integer> builder = ImmutableMap.builder();
202    for (Entry<? extends E> entry : entries) {
203      int count = entry.getCount();
204      if (count > 0) {
205        // Since ImmutableMap.Builder throws an NPE if an element is null, no
206        // other null checks are needed.
207        builder.put(entry.getElement(), count);
208        size += count;
209      }
210    }
211
212    if (size == 0) {
213      return of();
214    }
215    return new RegularImmutableMultiset<E>(
216        builder.build(), Ints.saturatedCast(size));
217  }
218
219  /**
220   * Returns an immutable multiset containing the given elements.
221   *
222   * <p>The multiset is ordered by the first occurrence of each element. For
223   * example,
224   * {@code ImmutableMultiset.copyOf(Arrays.asList(2, 3, 1, 3).iterator())}
225   * yields a multiset with elements in the order {@code 2, 3, 3, 1}.
226   *
227   * @throws NullPointerException if any of {@code elements} is null
228   */
229  public static <E> ImmutableMultiset<E> copyOf(
230      Iterator<? extends E> elements) {
231    Multiset<E> multiset = LinkedHashMultiset.create();
232    Iterators.addAll(multiset, elements);
233    return copyOfInternal(multiset);
234  }
235
236  ImmutableMultiset() {}
237
238  @Override public UnmodifiableIterator<E> iterator() {
239    final Iterator<Entry<E>> entryIterator = entrySet().iterator();
240    return new UnmodifiableIterator<E>() {
241      int remaining;
242      E element;
243
244      @Override
245      public boolean hasNext() {
246        return (remaining > 0) || entryIterator.hasNext();
247      }
248
249      @Override
250      public E next() {
251        if (remaining <= 0) {
252          Entry<E> entry = entryIterator.next();
253          element = entry.getElement();
254          remaining = entry.getCount();
255        }
256        remaining--;
257        return element;
258      }
259    };
260  }
261
262  @Override
263  public boolean contains(@Nullable Object object) {
264    return count(object) > 0;
265  }
266
267  @Override
268  public boolean containsAll(Collection<?> targets) {
269    return elementSet().containsAll(targets);
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  @Deprecated
279  @Override
280  public final int add(E element, int occurrences) {
281    throw new UnsupportedOperationException();
282  }
283
284  /**
285   * Guaranteed to throw an exception and leave the collection unmodified.
286   *
287   * @throws UnsupportedOperationException always
288   * @deprecated Unsupported operation.
289   */
290  @Deprecated
291  @Override
292  public final int remove(Object element, int occurrences) {
293    throw new UnsupportedOperationException();
294  }
295
296  /**
297   * Guaranteed to throw an exception and leave the collection unmodified.
298   *
299   * @throws UnsupportedOperationException always
300   * @deprecated Unsupported operation.
301   */
302  @Deprecated
303  @Override
304  public final int setCount(E element, int count) {
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  @Deprecated
315  @Override
316  public final boolean setCount(E element, int oldCount, int newCount) {
317    throw new UnsupportedOperationException();
318  }
319
320  @GwtIncompatible("not present in emulated superclass")
321  @Override
322  int copyIntoArray(Object[] dst, int offset) {
323    for (Multiset.Entry<E> entry : entrySet()) {
324      Arrays.fill(dst, offset, offset + entry.getCount(), entry.getElement());
325      offset += entry.getCount();
326    }
327    return offset;
328  }
329
330  @Override public boolean equals(@Nullable Object object) {
331    return Multisets.equalsImpl(this, object);
332  }
333
334  @Override public int hashCode() {
335    return Sets.hashCodeImpl(entrySet());
336  }
337
338  @Override public String toString() {
339    return entrySet().toString();
340  }
341
342  private transient ImmutableSet<Entry<E>> entrySet;
343
344  @Override
345  public ImmutableSet<Entry<E>> entrySet() {
346    ImmutableSet<Entry<E>> es = entrySet;
347    return (es == null) ? (entrySet = createEntrySet()) : es;
348  }
349
350  private final ImmutableSet<Entry<E>> createEntrySet() {
351    return isEmpty() ? ImmutableSet.<Entry<E>>of() : new EntrySet();
352  }
353
354  abstract Entry<E> getEntry(int index);
355
356  private final class EntrySet extends ImmutableSet<Entry<E>> {
357    @Override
358    boolean isPartialView() {
359      return ImmutableMultiset.this.isPartialView();
360    }
361
362    @Override
363    public UnmodifiableIterator<Entry<E>> iterator() {
364      return asList().iterator();
365    }
366
367    @Override
368    ImmutableList<Entry<E>> createAsList() {
369      return new ImmutableAsList<Entry<E>>() {
370        @Override
371        public Entry<E> get(int index) {
372          return getEntry(index);
373        }
374
375        @Override
376        ImmutableCollection<Entry<E>> delegateCollection() {
377          return EntrySet.this;
378        }
379      };
380    }
381
382    @Override
383    public int size() {
384      return elementSet().size();
385    }
386
387    @Override
388    public boolean contains(Object o) {
389      if (o instanceof Entry) {
390        Entry<?> entry = (Entry<?>) o;
391        if (entry.getCount() <= 0) {
392          return false;
393        }
394        int count = count(entry.getElement());
395        return count == entry.getCount();
396      }
397      return false;
398    }
399
400    @Override
401    public int hashCode() {
402      return ImmutableMultiset.this.hashCode();
403    }
404
405    // We can't label this with @Override, because it doesn't override anything
406    // in the GWT emulated version.
407    // TODO(cpovirk): try making all copies of this method @GwtIncompatible instead
408    Object writeReplace() {
409      return new EntrySetSerializedForm<E>(ImmutableMultiset.this);
410    }
411
412    private static final long serialVersionUID = 0;
413  }
414
415  static class EntrySetSerializedForm<E> implements Serializable {
416    final ImmutableMultiset<E> multiset;
417
418    EntrySetSerializedForm(ImmutableMultiset<E> multiset) {
419      this.multiset = multiset;
420    }
421
422    Object readResolve() {
423      return multiset.entrySet();
424    }
425  }
426
427  private static class SerializedForm implements Serializable {
428    final Object[] elements;
429    final int[] counts;
430
431    SerializedForm(Multiset<?> multiset) {
432      int distinct = multiset.entrySet().size();
433      elements = new Object[distinct];
434      counts = new int[distinct];
435      int i = 0;
436      for (Entry<?> entry : multiset.entrySet()) {
437        elements[i] = entry.getElement();
438        counts[i] = entry.getCount();
439        i++;
440      }
441    }
442
443    Object readResolve() {
444      LinkedHashMultiset<Object> multiset =
445          LinkedHashMultiset.create(elements.length);
446      for (int i = 0; i < elements.length; i++) {
447        multiset.add(elements[i], counts[i]);
448      }
449      return ImmutableMultiset.copyOf(multiset);
450    }
451
452    private static final long serialVersionUID = 0;
453  }
454
455  // We can't label this with @Override, because it doesn't override anything
456  // in the GWT emulated version.
457  Object writeReplace() {
458    return new SerializedForm(this);
459  }
460
461  /**
462   * Returns a new builder. The generated builder is equivalent to the builder
463   * created by the {@link Builder} constructor.
464   */
465  public static <E> Builder<E> builder() {
466    return new Builder<E>();
467  }
468
469  /**
470   * A builder for creating immutable multiset instances, especially {@code
471   * public static final} multisets ("constant multisets"). Example:
472   * <pre> {@code
473   *
474   *   public static final ImmutableMultiset<Bean> BEANS =
475   *       new ImmutableMultiset.Builder<Bean>()
476   *           .addCopies(Bean.COCOA, 4)
477   *           .addCopies(Bean.GARDEN, 6)
478   *           .addCopies(Bean.RED, 8)
479   *           .addCopies(Bean.BLACK_EYED, 10)
480   *           .build();}</pre>
481   *
482   * <p>Builder instances can be reused; it is safe to call {@link #build} multiple
483   * times to build multiple multisets in series.
484   *
485   * @since 2.0 (imported from Google Collections Library)
486   */
487  public static class Builder<E> extends ImmutableCollection.Builder<E> {
488    final Multiset<E> contents;
489
490    /**
491     * Creates a new builder. The returned builder is equivalent to the builder
492     * generated by {@link ImmutableMultiset#builder}.
493     */
494    public Builder() {
495      this(LinkedHashMultiset.<E>create());
496    }
497
498    Builder(Multiset<E> contents) {
499      this.contents = contents;
500    }
501
502    /**
503     * Adds {@code element} to the {@code ImmutableMultiset}.
504     *
505     * @param element the element to add
506     * @return this {@code Builder} object
507     * @throws NullPointerException if {@code element} is null
508     */
509    @Override public Builder<E> add(E element) {
510      contents.add(checkNotNull(element));
511      return this;
512    }
513
514    /**
515     * Adds a number of occurrences of an element to this {@code
516     * ImmutableMultiset}.
517     *
518     * @param element the element to add
519     * @param occurrences the number of occurrences of the element to add. May
520     *     be zero, in which case no change will be made.
521     * @return this {@code Builder} object
522     * @throws NullPointerException if {@code element} is null
523     * @throws IllegalArgumentException if {@code occurrences} is negative, or
524     *     if this operation would result in more than {@link Integer#MAX_VALUE}
525     *     occurrences of the element
526     */
527    public Builder<E> addCopies(E element, int occurrences) {
528      contents.add(checkNotNull(element), occurrences);
529      return this;
530    }
531
532    /**
533     * Adds or removes the necessary occurrences of an element such that the
534     * element attains the desired count.
535     *
536     * @param element the element to add or remove occurrences of
537     * @param count the desired count of the element in this multiset
538     * @return this {@code Builder} object
539     * @throws NullPointerException if {@code element} is null
540     * @throws IllegalArgumentException if {@code count} is negative
541     */
542    public Builder<E> setCount(E element, int count) {
543      contents.setCount(checkNotNull(element), count);
544      return this;
545    }
546
547    /**
548     * Adds each element of {@code elements} to the {@code ImmutableMultiset}.
549     *
550     * @param elements the elements to add
551     * @return this {@code Builder} object
552     * @throws NullPointerException if {@code elements} is null or contains a
553     *     null element
554     */
555    @Override public Builder<E> add(E... elements) {
556      super.add(elements);
557      return this;
558    }
559
560    /**
561     * Adds each element of {@code elements} to the {@code ImmutableMultiset}.
562     *
563     * @param elements the {@code Iterable} to add to the {@code
564     *     ImmutableMultiset}
565     * @return this {@code Builder} object
566     * @throws NullPointerException if {@code elements} is null or contains a
567     *     null element
568     */
569    @Override public Builder<E> addAll(Iterable<? extends E> elements) {
570      if (elements instanceof Multiset) {
571        Multiset<? extends E> multiset = Multisets.cast(elements);
572        for (Entry<? extends E> entry : multiset.entrySet()) {
573          addCopies(entry.getElement(), entry.getCount());
574        }
575      } else {
576        super.addAll(elements);
577      }
578      return this;
579    }
580
581    /**
582     * Adds each element of {@code elements} to the {@code ImmutableMultiset}.
583     *
584     * @param elements the elements to add to the {@code ImmutableMultiset}
585     * @return this {@code Builder} object
586     * @throws NullPointerException if {@code elements} is null or contains a
587     *     null element
588     */
589    @Override public Builder<E> addAll(Iterator<? extends E> elements) {
590      super.addAll(elements);
591      return this;
592    }
593
594    /**
595     * Returns a newly-created {@code ImmutableMultiset} based on the contents
596     * of the {@code Builder}.
597     */
598    @Override public ImmutableMultiset<E> build() {
599      return copyOf(contents);
600    }
601  }
602}