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