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.annotations.GwtIncompatible;
023    import com.google.common.collect.Serialization.FieldSetter;
024    import com.google.common.primitives.Ints;
025    
026    import java.io.IOException;
027    import java.io.InvalidObjectException;
028    import java.io.ObjectInputStream;
029    import java.io.ObjectOutputStream;
030    import java.util.ArrayList;
031    import java.util.Arrays;
032    import java.util.Collections;
033    import java.util.Iterator;
034    import java.util.List;
035    import java.util.Map;
036    import java.util.Set;
037    
038    import 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
053    public 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    }