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