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    }