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