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.Serialization.FieldSetter;
024import com.google.common.primitives.Ints;
025
026import java.io.IOException;
027import java.io.InvalidObjectException;
028import java.io.ObjectInputStream;
029import java.io.ObjectOutputStream;
030import java.util.ArrayList;
031import java.util.Arrays;
032import java.util.Collections;
033import java.util.Iterator;
034import java.util.List;
035import java.util.Map;
036import java.util.Set;
037
038import javax.annotation.Nullable;
039
040/**
041 * An immutable hash-based multiset. Does not permit null elements.
042 *
043 * <p>Its iterator orders elements according to the first appearance of the
044 * element among the items passed to the factory method or builder. When the
045 * multiset contains multiple instances of an element, those instances are
046 * consecutive in the iteration order.
047 *
048 * @author Jared Levy
049 * @since 2 (imported from Google Collections Library)
050 */
051@GwtCompatible(serializable = true, emulated = true)
052// TODO(user): write an efficient asList() implementation
053public 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 (source-compatible since release 2)
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 (source-compatible since release 2)
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 (source-compatible since release 2)
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 (source-compatible since release 2)
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 (source-compatible since release 2)
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 (source-compatible since release 2)
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.of(2, 3, 1, 3)} yields a multiset with
140   * elements in the order {@code 2, 3, 3, 1}.
141   *
142   * @throws NullPointerException if any of {@code elements} is null
143   * @deprecated use {@link #copyOf(Object[])}. <b>This method is scheduled for
144   *     deletion in January 2012.</b>
145   * @since 2 (changed from varargs in release 6)
146   */
147  @Deprecated
148  public static <E> ImmutableMultiset<E> of(E[] elements) {
149    return copyOf(Arrays.asList(elements));
150  }
151
152  /**
153   * Returns an immutable multiset containing the given elements.
154   *
155   * <p>The multiset is ordered by the first occurrence of each element. For
156   * example, {@code ImmutableMultiset.copyOf([2, 3, 1, 3])} yields a multiset
157   * with elements in the order {@code 2, 3, 3, 1}.
158   *
159   * @throws NullPointerException if any of {@code elements} is null
160   * @since 6
161   */
162  public static <E> ImmutableMultiset<E> copyOf(E[] elements) {
163    return copyOf(Arrays.asList(elements));
164  }
165
166  /**
167   * Returns an immutable multiset containing the given elements.
168   *
169   * <p>The multiset is ordered by the first occurrence of each element. For
170   * example, {@code ImmutableMultiset.copyOf(Arrays.asList(2, 3, 1, 3))} yields
171   * a multiset with elements in the order {@code 2, 3, 3, 1}.
172   *
173   * <p>Despite the method name, this method attempts to avoid actually copying
174   * the data when it is safe to do so. The exact circumstances under which a
175   * copy will or will not be performed are undocumented and subject to change.
176   *
177   * <p><b>Note:</b> Despite what the method name suggests, if {@code elements}
178   * is an {@code ImmutableMultiset}, no copy will actually be performed, and
179   * the given multiset itself will be returned.
180   *
181   * @throws NullPointerException if any of {@code elements} is null
182   */
183  public static <E> ImmutableMultiset<E> copyOf(
184      Iterable<? extends E> elements) {
185    if (elements instanceof ImmutableMultiset) {
186      @SuppressWarnings("unchecked") // all supported methods are covariant
187      ImmutableMultiset<E> result = (ImmutableMultiset<E>) elements;
188      if (!result.isPartialView()) {
189        return result;
190      }
191    }
192
193    Multiset<? extends E> multiset = (elements instanceof Multiset)
194        ? Multisets.cast(elements)
195        : LinkedHashMultiset.create(elements);
196
197    return copyOfInternal(multiset);
198  }
199
200  private static <E> ImmutableMultiset<E> copyOfInternal(E... elements) {
201    return copyOf(Arrays.asList(elements));
202  }
203
204  private static <E> ImmutableMultiset<E> copyOfInternal(
205      Multiset<? extends E> multiset) {
206    long size = 0;
207    ImmutableMap.Builder<E, Integer> builder = ImmutableMap.builder();
208
209    for (Entry<? extends E> entry : multiset.entrySet()) {
210      int count = entry.getCount();
211      if (count > 0) {
212        // Since ImmutableMap.Builder throws an NPE if an element is null, no
213        // other null checks are needed.
214        builder.put(entry.getElement(), count);
215        size += count;
216      }
217    }
218
219    if (size == 0) {
220      return of();
221    }
222    return new ImmutableMultiset<E>(builder.build(), Ints.saturatedCast(size));
223  }
224
225  /**
226   * Returns an immutable multiset containing the given elements.
227   *
228   * <p>The multiset is ordered by the first occurrence of each element. For
229   * example,
230   * {@code ImmutableMultiset.copyOf(Arrays.asList(2, 3, 1, 3).iterator())}
231   * yields a multiset with elements in the order {@code 2, 3, 3, 1}.
232   *
233   * @throws NullPointerException if any of {@code elements} is null
234   */
235  public static <E> ImmutableMultiset<E> copyOf(
236      Iterator<? extends E> elements) {
237    Multiset<E> multiset = LinkedHashMultiset.create();
238    Iterators.addAll(multiset, elements);
239    return copyOfInternal(multiset);
240  }
241
242  private final transient ImmutableMap<E, Integer> map;
243  private final transient int size;
244
245  // These constants allow the deserialization code to set final fields. This
246  // holder class makes sure they are not initialized unless an instance is
247  // deserialized.
248  @GwtIncompatible("java serialization is not supported.")
249  @SuppressWarnings("unchecked")
250  // eclipse doesn't like the raw types here, but they're harmless
251  private static class FieldSettersHolder {
252    static final FieldSetter<ImmutableMultiset> MAP_FIELD_SETTER
253        = Serialization.getFieldSetter(ImmutableMultiset.class, "map");
254    static final FieldSetter<ImmutableMultiset> SIZE_FIELD_SETTER
255        = Serialization.getFieldSetter(ImmutableMultiset.class, "size");
256  }
257
258  ImmutableMultiset(ImmutableMap<E, Integer> map, int size) {
259    this.map = map;
260    this.size = size;
261  }
262
263  @Override boolean isPartialView() {
264    return map.isPartialView();
265  }
266
267  @Override
268  public int count(@Nullable Object element) {
269    Integer value = map.get(element);
270    return (value == null) ? 0 : value;
271  }
272
273  @Override public UnmodifiableIterator<E> iterator() {
274    final Iterator<Map.Entry<E, Integer>> mapIterator
275        = map.entrySet().iterator();
276
277    return new UnmodifiableIterator<E>() {
278      int remaining;
279      E element;
280
281      @Override
282      public boolean hasNext() {
283        return (remaining > 0) || mapIterator.hasNext();
284      }
285
286      @Override
287      public E next() {
288        if (remaining <= 0) {
289          Map.Entry<E, Integer> entry = mapIterator.next();
290          element = entry.getKey();
291          remaining = entry.getValue();
292        }
293        remaining--;
294        return element;
295      }
296    };
297  }
298
299  @Override
300  public int size() {
301    return size;
302  }
303
304  @Override public boolean contains(@Nullable Object element) {
305    return map.containsKey(element);
306  }
307
308  /**
309   * Guaranteed to throw an exception and leave the collection unmodified.
310   *
311   * @throws UnsupportedOperationException always
312   */
313  @Override
314  public int add(E element, int occurrences) {
315    throw new UnsupportedOperationException();
316  }
317
318  /**
319   * Guaranteed to throw an exception and leave the collection unmodified.
320   *
321   * @throws UnsupportedOperationException always
322   */
323  @Override
324  public int remove(Object element, int occurrences) {
325    throw new UnsupportedOperationException();
326  }
327
328  /**
329   * Guaranteed to throw an exception and leave the collection unmodified.
330   *
331   * @throws UnsupportedOperationException always
332   */
333  @Override
334  public int setCount(E element, int count) {
335    throw new UnsupportedOperationException();
336  }
337
338  /**
339   * Guaranteed to throw an exception and leave the collection unmodified.
340   *
341   * @throws UnsupportedOperationException always
342   */
343  @Override
344  public boolean setCount(E element, int oldCount, int newCount) {
345    throw new UnsupportedOperationException();
346  }
347
348  @Override public boolean equals(@Nullable Object object) {
349    if (object == this) {
350      return true;
351    }
352    if (object instanceof Multiset) {
353      Multiset<?> that = (Multiset<?>) object;
354      if (this.size() != that.size()) {
355        return false;
356      }
357      for (Entry<?> entry : that.entrySet()) {
358        if (count(entry.getElement()) != entry.getCount()) {
359          return false;
360        }
361      }
362      return true;
363    }
364    return false;
365  }
366
367  @Override public int hashCode() {
368    // could cache this, but not considered worthwhile to do so
369    return map.hashCode();
370  }
371
372  @Override public String toString() {
373    return entrySet().toString();
374  }
375
376  @Override
377  public Set<E> elementSet() {
378    return map.keySet();
379  }
380
381  private transient ImmutableSet<Entry<E>> entrySet;
382
383  @Override
384  public Set<Entry<E>> entrySet() {
385    ImmutableSet<Entry<E>> es = entrySet;
386    return (es == null) ? (entrySet = new EntrySet<E>(this)) : es;
387  }
388
389  private static class EntrySet<E> extends ImmutableSet<Entry<E>> {
390    final ImmutableMultiset<E> multiset;
391
392    public EntrySet(ImmutableMultiset<E> multiset) {
393      this.multiset = multiset;
394    }
395
396    @Override public UnmodifiableIterator<Entry<E>> iterator() {
397      final Iterator<Map.Entry<E, Integer>> mapIterator
398          = multiset.map.entrySet().iterator();
399      return new UnmodifiableIterator<Entry<E>>() {
400        @Override
401        public boolean hasNext() {
402          return mapIterator.hasNext();
403        }
404        @Override
405        public Entry<E> next() {
406          Map.Entry<E, Integer> mapEntry = mapIterator.next();
407          return
408              Multisets.immutableEntry(mapEntry.getKey(), mapEntry.getValue());
409        }
410      };
411    }
412
413    @Override
414    public int size() {
415      return multiset.map.size();
416    }
417
418    @Override boolean isPartialView() {
419      return multiset.isPartialView();
420    }
421
422    @Override public boolean contains(Object o) {
423      if (o instanceof Entry) {
424        Entry<?> entry = (Entry<?>) o;
425        if (entry.getCount() <= 0) {
426          return false;
427        }
428        int count = multiset.count(entry.getElement());
429        return count == entry.getCount();
430      }
431      return false;
432    }
433
434    // TODO(hhchan): Revert once this class is emulated in GWT.
435    @Override public Object[] toArray() {
436      Object[] newArray = new Object[size()];
437      return toArray(newArray);
438    }
439
440    // TODO(hhchan): Revert once this class is emulated in GWT.
441    @Override public <T> T[] toArray(T[] other) {
442      int size = size();
443      if (other.length < size) {
444        other = ObjectArrays.newArray(other, size);
445      } else if (other.length > size) {
446        other[size] = null;
447      }
448
449      // Writes will produce ArrayStoreException when the toArray() doc requires
450      Object[] otherAsObjectArray = other;
451      int index = 0;
452      for (Entry<?> element : this) {
453        otherAsObjectArray[index++] = element;
454      }
455      return other;
456    }
457
458    @Override public int hashCode() {
459      return multiset.map.hashCode();
460    }
461
462    @GwtIncompatible("not needed in emulated source.")
463    @Override Object writeReplace() {
464      return this;
465    }
466
467    private static final long serialVersionUID = 0;
468  }
469
470  /**
471   * @serialData the number of distinct elements, the first element, its count,
472   *     the second element, its count, and so on
473   */
474  @GwtIncompatible("java.io.ObjectOutputStream")
475  private void writeObject(ObjectOutputStream stream) throws IOException {
476    stream.defaultWriteObject();
477    Serialization.writeMultiset(this, stream);
478  }
479
480  @GwtIncompatible("java.io.ObjectInputStream")
481  private void readObject(ObjectInputStream stream)
482      throws IOException, ClassNotFoundException {
483    stream.defaultReadObject();
484    int entryCount = stream.readInt();
485    ImmutableMap.Builder<E, Integer> builder = ImmutableMap.builder();
486    long tmpSize = 0;
487    for (int i = 0; i < entryCount; i++) {
488      @SuppressWarnings("unchecked") // reading data stored by writeMultiset
489      E element = (E) stream.readObject();
490      int count = stream.readInt();
491      if (count <= 0) {
492        throw new InvalidObjectException("Invalid count " + count);
493      }
494      builder.put(element, count);
495      tmpSize += count;
496    }
497
498    FieldSettersHolder.MAP_FIELD_SETTER.set(this, builder.build());
499    FieldSettersHolder.SIZE_FIELD_SETTER.set(this, Ints.saturatedCast(tmpSize));
500  }
501
502  @GwtIncompatible("java serialization not supported.")
503  @Override Object writeReplace() {
504    return this;
505  }
506
507  private static final long serialVersionUID = 0;
508
509  /**
510   * Returns a new builder. The generated builder is equivalent to the builder
511   * created by the {@link Builder} constructor.
512   */
513  public static <E> Builder<E> builder() {
514    return new Builder<E>();
515  }
516
517  /**
518   * A builder for creating immutable multiset instances, especially {@code
519   * public static final} multisets ("constant multisets"). Example:
520   * <pre> {@code
521   *
522   *   public static final ImmutableMultiset<Bean> BEANS =
523   *       new ImmutableMultiset.Builder<Bean>()
524   *           .addCopies(Bean.COCOA, 4)
525   *           .addCopies(Bean.GARDEN, 6)
526   *           .addCopies(Bean.RED, 8)
527   *           .addCopies(Bean.BLACK_EYED, 10)
528   *           .build();}</pre>
529   *
530   * Builder instances can be reused; it is safe to call {@link #build} multiple
531   * times to build multiple multisets in series. Each multiset is a superset of
532   * the multiset created before it.
533   *
534   * @since 2 (imported from Google Collections Library)
535   */
536  public static final class Builder<E> extends ImmutableCollection.Builder<E> {
537    private final Multiset<E> contents = LinkedHashMultiset.create();
538
539    /**
540     * Creates a new builder. The returned builder is equivalent to the builder
541     * generated by {@link ImmutableMultiset#builder}.
542     */
543    public Builder() {}
544
545    /**
546     * Adds {@code element} to the {@code ImmutableMultiset}.
547     *
548     * @param element the element to add
549     * @return this {@code Builder} object
550     * @throws NullPointerException if {@code element} is null
551     */
552    @Override public Builder<E> add(E element) {
553      contents.add(checkNotNull(element));
554      return this;
555    }
556
557    /**
558     * Adds a number of occurrences of an element to this {@code
559     * ImmutableMultiset}.
560     *
561     * @param element the element to add
562     * @param occurrences the number of occurrences of the element to add. May
563     *     be zero, in which case no change will be made.
564     * @return this {@code Builder} object
565     * @throws NullPointerException if {@code element} is null
566     * @throws IllegalArgumentException if {@code occurrences} is negative, or
567     *     if this operation would result in more than {@link Integer#MAX_VALUE}
568     *     occurrences of the element
569     */
570    public Builder<E> addCopies(E element, int occurrences) {
571      contents.add(checkNotNull(element), occurrences);
572      return this;
573    }
574
575    /**
576     * Adds or removes the necessary occurrences of an element such that the
577     * element attains the desired count.
578     *
579     * @param element the element to add or remove occurrences of
580     * @param count the desired count of the element in this multiset
581     * @return this {@code Builder} object
582     * @throws NullPointerException if {@code element} is null
583     * @throws IllegalArgumentException if {@code count} is negative
584     */
585    public Builder<E> setCount(E element, int count) {
586      contents.setCount(checkNotNull(element), count);
587      return this;
588    }
589
590    /**
591     * Adds each element of {@code elements} to the {@code ImmutableMultiset}.
592     *
593     * @param elements the elements to add
594     * @return this {@code Builder} object
595     * @throws NullPointerException if {@code elements} is null or contains a
596     *     null element
597     */
598    @Override public Builder<E> add(E... elements) {
599      super.add(elements);
600      return this;
601    }
602
603    /**
604     * Adds each element of {@code elements} to the {@code ImmutableMultiset}.
605     *
606     * @param elements the {@code Iterable} to add to the {@code
607     *     ImmutableMultiset}
608     * @return this {@code Builder} object
609     * @throws NullPointerException if {@code elements} is null or contains a
610     *     null element
611     */
612    @Override public Builder<E> addAll(Iterable<? extends E> elements) {
613      if (elements instanceof Multiset) {
614        Multiset<? extends E> multiset = Multisets.cast(elements);
615        for (Entry<? extends E> entry : multiset.entrySet()) {
616          addCopies(entry.getElement(), entry.getCount());
617        }
618      } else {
619        super.addAll(elements);
620      }
621      return this;
622    }
623
624    /**
625     * Adds each element of {@code elements} to the {@code ImmutableMultiset}.
626     *
627     * @param elements the elements to add to the {@code ImmutableMultiset}
628     * @return this {@code Builder} object
629     * @throws NullPointerException if {@code elements} is null or contains a
630     *     null element
631     */
632    @Override public Builder<E> addAll(Iterator<? extends E> elements) {
633      super.addAll(elements);
634      return this;
635    }
636
637    /**
638     * Returns a newly-created {@code ImmutableMultiset} based on the contents
639     * of the {@code Builder}.
640     */
641    @Override public ImmutableMultiset<E> build() {
642      return copyOf(contents);
643    }
644  }
645}