View Javadoc
1   /*
2    * Copyright (C) 2008 The Guava Authors
3    *
4    * Licensed under the Apache License, Version 2.0 (the "License");
5    * you may not use this file except in compliance with the License.
6    * You may obtain a copy of the License at
7    *
8    * http://www.apache.org/licenses/LICENSE-2.0
9    *
10   * Unless required by applicable law or agreed to in writing, software
11   * distributed under the License is distributed on an "AS IS" BASIS,
12   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13   * See the License for the specific language governing permissions and
14   * limitations under the License.
15   */
16  
17  package com.google.common.collect;
18  
19  import static com.google.common.base.Preconditions.checkNotNull;
20  
21  import com.google.common.annotations.Beta;
22  import com.google.common.annotations.GwtCompatible;
23  import com.google.common.annotations.GwtIncompatible;
24  import com.google.errorprone.annotations.CanIgnoreReturnValue;
25  import com.google.errorprone.annotations.concurrent.LazyInit;
26  import com.google.j2objc.annotations.WeakOuter;
27  import java.io.Serializable;
28  import java.util.Arrays;
29  import java.util.Collection;
30  import java.util.Collections;
31  import java.util.Iterator;
32  import java.util.function.Function;
33  import java.util.function.ToIntFunction;
34  import java.util.stream.Collector;
35  import javax.annotation.Nullable;
36  
37  /**
38   * A {@link Multiset} whose contents will never change, with many other important properties
39   * detailed at {@link ImmutableCollection}.
40   *
41   * <p><b>Grouped iteration.</b> In all current implementations, duplicate elements always appear
42   * consecutively when iterating. Elements iterate in order by the <i>first</i> appearance of
43   * that element when the multiset was created.
44   *
45   * <p>See the Guava User Guide article on <a href=
46   * "https://github.com/google/guava/wiki/ImmutableCollectionsExplained">
47   * immutable collections</a>.
48   *
49   * @author Jared Levy
50   * @author Louis Wasserman
51   * @since 2.0
52   */
53  @GwtCompatible(serializable = true, emulated = true)
54  @SuppressWarnings("serial") // we're overriding default serialization
55  public abstract class ImmutableMultiset<E> extends ImmutableMultisetGwtSerializationDependencies<E>
56      implements Multiset<E> {
57  
58    /**
59     * Returns a {@code Collector} that accumulates the input elements into a new
60     * {@code ImmutableMultiset}.  Elements iterate in order by the <i>first</i> appearance of that
61     * element in encounter order.
62     *
63     * @since 21.0
64     */
65    @Beta
66    public static <E> Collector<E, ?, ImmutableMultiset<E>> toImmutableMultiset() {
67      return toImmutableMultiset(Function.identity(), e -> 1);
68    }
69  
70    /**
71     * Returns a {@code Collector} that accumulates elements into an {@code ImmutableMultiset} whose
72     * elements are the result of applying {@code elementFunction} to the inputs, with counts equal to
73     * the result of applying {@code countFunction} to the inputs.
74     *
75     * <p>If the mapped elements contain duplicates (according to {@link Object#equals}), the first
76     * occurrence in encounter order appears in the resulting multiset, with count equal to the sum of
77     * the outputs of {@code countFunction.applyAsInt(t)} for each {@code t} mapped to that element.
78     *
79     * @since 22.0
80     */
81    public static <T, E> Collector<T, ?, ImmutableMultiset<E>> toImmutableMultiset(
82        Function<? super T, ? extends E> elementFunction, ToIntFunction<? super T> countFunction) {
83      checkNotNull(elementFunction);
84      checkNotNull(countFunction);
85      return Collector.of(
86          LinkedHashMultiset::create,
87          (multiset, t) ->
88              multiset.add(checkNotNull(elementFunction.apply(t)), countFunction.applyAsInt(t)),
89          (multiset1, multiset2) -> {
90            multiset1.addAll(multiset2);
91            return multiset1;
92          },
93          (Multiset<E> multiset) -> copyFromEntries(multiset.entrySet()));
94    }
95  
96    /**
97     * Returns the empty immutable multiset.
98     */
99    @SuppressWarnings("unchecked") // all supported methods are covariant
100   public static <E> ImmutableMultiset<E> of() {
101     return (ImmutableMultiset<E>) RegularImmutableMultiset.EMPTY;
102   }
103 
104   /**
105    * Returns an immutable multiset containing a single element.
106    *
107    * @throws NullPointerException if {@code element} is null
108    * @since 6.0 (source-compatible since 2.0)
109    */
110   @SuppressWarnings("unchecked") // generic array created but never written
111   public static <E> ImmutableMultiset<E> of(E element) {
112     return copyFromElements(element);
113   }
114 
115   /**
116    * Returns an immutable multiset containing the given elements, in order.
117    *
118    * @throws NullPointerException if any element is null
119    * @since 6.0 (source-compatible since 2.0)
120    */
121   @SuppressWarnings("unchecked") //
122   public static <E> ImmutableMultiset<E> of(E e1, E e2) {
123     return copyFromElements(e1, e2);
124   }
125 
126   /**
127    * Returns an immutable multiset containing the given elements, in the "grouped iteration order"
128    * described in the class documentation.
129    *
130    * @throws NullPointerException if any element is null
131    * @since 6.0 (source-compatible since 2.0)
132    */
133   @SuppressWarnings("unchecked") //
134   public static <E> ImmutableMultiset<E> of(E e1, E e2, E e3) {
135     return copyFromElements(e1, e2, e3);
136   }
137 
138   /**
139    * Returns an immutable multiset containing the given elements, in the "grouped iteration order"
140    * described in the class documentation.
141    *
142    * @throws NullPointerException if any element is null
143    * @since 6.0 (source-compatible since 2.0)
144    */
145   @SuppressWarnings("unchecked") //
146   public static <E> ImmutableMultiset<E> of(E e1, E e2, E e3, E e4) {
147     return copyFromElements(e1, e2, e3, e4);
148   }
149 
150   /**
151    * Returns an immutable multiset containing the given elements, in the "grouped iteration order"
152    * described in the class documentation.
153    *
154    * @throws NullPointerException if any element is null
155    * @since 6.0 (source-compatible since 2.0)
156    */
157   @SuppressWarnings("unchecked") //
158   public static <E> ImmutableMultiset<E> of(E e1, E e2, E e3, E e4, E e5) {
159     return copyFromElements(e1, e2, e3, e4, e5);
160   }
161 
162   /**
163    * Returns an immutable multiset containing the given elements, in the "grouped iteration order"
164    * described in the class documentation.
165    *
166    * @throws NullPointerException if any element is null
167    * @since 6.0 (source-compatible since 2.0)
168    */
169   @SuppressWarnings("unchecked") //
170   public static <E> ImmutableMultiset<E> of(E e1, E e2, E e3, E e4, E e5, E e6, E... others) {
171     return new Builder<E>().add(e1).add(e2).add(e3).add(e4).add(e5).add(e6).add(others).build();
172   }
173 
174   /**
175    * Returns an immutable multiset containing the given elements, in the "grouped iteration order"
176    * described in the class documentation.
177    *
178    * @throws NullPointerException if any of {@code elements} is null
179    * @since 6.0
180    */
181   public static <E> ImmutableMultiset<E> copyOf(E[] elements) {
182     return copyFromElements(elements);
183   }
184 
185   /**
186    * Returns an immutable multiset containing the given elements, in the "grouped iteration order"
187    * described in the class documentation.
188    *
189    * @throws NullPointerException if any of {@code elements} is null
190    */
191   public static <E> ImmutableMultiset<E> copyOf(Iterable<? extends E> elements) {
192     if (elements instanceof ImmutableMultiset) {
193       @SuppressWarnings("unchecked") // all supported methods are covariant
194       ImmutableMultiset<E> result = (ImmutableMultiset<E>) elements;
195       if (!result.isPartialView()) {
196         return result;
197       }
198     }
199 
200     Multiset<? extends E> multiset =
201         (elements instanceof Multiset)
202             ? Multisets.cast(elements)
203             : LinkedHashMultiset.create(elements);
204 
205     return copyFromEntries(multiset.entrySet());
206   }
207 
208   private static <E> ImmutableMultiset<E> copyFromElements(E... elements) {
209     Multiset<E> multiset = LinkedHashMultiset.create();
210     Collections.addAll(multiset, elements);
211     return copyFromEntries(multiset.entrySet());
212   }
213 
214   static <E> ImmutableMultiset<E> copyFromEntries(
215       Collection<? extends Entry<? extends E>> entries) {
216     if (entries.isEmpty()) {
217       return of();
218     } else {
219       return new RegularImmutableMultiset<E>(entries);
220     }
221   }
222 
223   /**
224    * Returns an immutable multiset containing the given elements, in the "grouped iteration order"
225    * described in the class documentation.
226    *
227    * @throws NullPointerException if any of {@code elements} is null
228    */
229   public static <E> ImmutableMultiset<E> copyOf(Iterator<? extends E> elements) {
230     Multiset<E> multiset = LinkedHashMultiset.create();
231     Iterators.addAll(multiset, elements);
232     return copyFromEntries(multiset.entrySet());
233   }
234 
235   ImmutableMultiset() {}
236 
237   @Override
238   public UnmodifiableIterator<E> iterator() {
239     final Iterator<Entry<E>> entryIterator = entrySet().iterator();
240     return new UnmodifiableIterator<E>() {
241       int remaining;
242       E element;
243 
244       @Override
245       public boolean hasNext() {
246         return (remaining > 0) || entryIterator.hasNext();
247       }
248 
249       @Override
250       public E next() {
251         if (remaining <= 0) {
252           Entry<E> entry = entryIterator.next();
253           element = entry.getElement();
254           remaining = entry.getCount();
255         }
256         remaining--;
257         return element;
258       }
259     };
260   }
261 
262   @LazyInit
263   private transient ImmutableList<E> asList;
264 
265   @Override
266   public ImmutableList<E> asList() {
267     ImmutableList<E> result = asList;
268     return (result == null) ? asList = super.asList() : result;
269   }
270 
271   @Override
272   public boolean contains(@Nullable Object object) {
273     return count(object) > 0;
274   }
275 
276   /**
277    * Guaranteed to throw an exception and leave the collection unmodified.
278    *
279    * @throws UnsupportedOperationException always
280    * @deprecated Unsupported operation.
281    */
282   @CanIgnoreReturnValue
283   @Deprecated
284   @Override
285   public final int add(E element, int occurrences) {
286     throw new UnsupportedOperationException();
287   }
288 
289   /**
290    * Guaranteed to throw an exception and leave the collection unmodified.
291    *
292    * @throws UnsupportedOperationException always
293    * @deprecated Unsupported operation.
294    */
295   @CanIgnoreReturnValue
296   @Deprecated
297   @Override
298   public final int remove(Object element, int occurrences) {
299     throw new UnsupportedOperationException();
300   }
301 
302   /**
303    * Guaranteed to throw an exception and leave the collection unmodified.
304    *
305    * @throws UnsupportedOperationException always
306    * @deprecated Unsupported operation.
307    */
308   @CanIgnoreReturnValue
309   @Deprecated
310   @Override
311   public final int setCount(E element, int count) {
312     throw new UnsupportedOperationException();
313   }
314 
315   /**
316    * Guaranteed to throw an exception and leave the collection unmodified.
317    *
318    * @throws UnsupportedOperationException always
319    * @deprecated Unsupported operation.
320    */
321   @CanIgnoreReturnValue
322   @Deprecated
323   @Override
324   public final boolean setCount(E element, int oldCount, int newCount) {
325     throw new UnsupportedOperationException();
326   }
327 
328   @GwtIncompatible // not present in emulated superclass
329   @Override
330   int copyIntoArray(Object[] dst, int offset) {
331     for (Multiset.Entry<E> entry : entrySet()) {
332       Arrays.fill(dst, offset, offset + entry.getCount(), entry.getElement());
333       offset += entry.getCount();
334     }
335     return offset;
336   }
337 
338   @Override
339   public boolean equals(@Nullable Object object) {
340     return Multisets.equalsImpl(this, object);
341   }
342 
343   @Override
344   public int hashCode() {
345     return Sets.hashCodeImpl(entrySet());
346   }
347 
348   @Override
349   public String toString() {
350     return entrySet().toString();
351   }
352 
353   /** @since 21.0 (present with return type {@code Set} since 2.0) */
354   @Override
355   public abstract ImmutableSet<E> elementSet();
356 
357   @LazyInit
358   private transient ImmutableSet<Entry<E>> entrySet;
359 
360   @Override
361   public ImmutableSet<Entry<E>> entrySet() {
362     ImmutableSet<Entry<E>> es = entrySet;
363     return (es == null) ? (entrySet = createEntrySet()) : es;
364   }
365 
366   private final ImmutableSet<Entry<E>> createEntrySet() {
367     return isEmpty() ? ImmutableSet.<Entry<E>>of() : new EntrySet();
368   }
369 
370   abstract Entry<E> getEntry(int index);
371 
372   @WeakOuter
373   private final class EntrySet extends ImmutableSet.Indexed<Entry<E>> {
374     @Override
375     boolean isPartialView() {
376       return ImmutableMultiset.this.isPartialView();
377     }
378 
379     @Override
380     Entry<E> get(int index) {
381       return getEntry(index);
382     }
383 
384     @Override
385     public int size() {
386       return elementSet().size();
387     }
388 
389     @Override
390     public boolean contains(Object o) {
391       if (o instanceof Entry) {
392         Entry<?> entry = (Entry<?>) o;
393         if (entry.getCount() <= 0) {
394           return false;
395         }
396         int count = count(entry.getElement());
397         return count == entry.getCount();
398       }
399       return false;
400     }
401 
402     @Override
403     public int hashCode() {
404       return ImmutableMultiset.this.hashCode();
405     }
406 
407     // We can't label this with @Override, because it doesn't override anything
408     // in the GWT emulated version.
409     // TODO(cpovirk): try making all copies of this method @GwtIncompatible instead
410     Object writeReplace() {
411       return new EntrySetSerializedForm<E>(ImmutableMultiset.this);
412     }
413 
414     private static final long serialVersionUID = 0;
415   }
416 
417   static class EntrySetSerializedForm<E> implements Serializable {
418     final ImmutableMultiset<E> multiset;
419 
420     EntrySetSerializedForm(ImmutableMultiset<E> multiset) {
421       this.multiset = multiset;
422     }
423 
424     Object readResolve() {
425       return multiset.entrySet();
426     }
427   }
428 
429   private static class SerializedForm implements Serializable {
430     final Object[] elements;
431     final int[] counts;
432 
433     SerializedForm(Multiset<?> multiset) {
434       int distinct = multiset.entrySet().size();
435       elements = new Object[distinct];
436       counts = new int[distinct];
437       int i = 0;
438       for (Entry<?> entry : multiset.entrySet()) {
439         elements[i] = entry.getElement();
440         counts[i] = entry.getCount();
441         i++;
442       }
443     }
444 
445     Object readResolve() {
446       LinkedHashMultiset<Object> multiset = LinkedHashMultiset.create(elements.length);
447       for (int i = 0; i < elements.length; i++) {
448         multiset.add(elements[i], counts[i]);
449       }
450       return ImmutableMultiset.copyOf(multiset);
451     }
452 
453     private static final long serialVersionUID = 0;
454   }
455 
456   // We can't label this with @Override, because it doesn't override anything
457   // in the GWT emulated version.
458   Object writeReplace() {
459     return new SerializedForm(this);
460   }
461 
462   /**
463    * Returns a new builder. The generated builder is equivalent to the builder
464    * created by the {@link Builder} constructor.
465    */
466   public static <E> Builder<E> builder() {
467     return new Builder<E>();
468   }
469 
470   /**
471    * A builder for creating immutable multiset instances, especially {@code
472    * public static final} multisets ("constant multisets"). Example:
473    * <pre> {@code
474    *
475    *   public static final ImmutableMultiset<Bean> BEANS =
476    *       new ImmutableMultiset.Builder<Bean>()
477    *           .addCopies(Bean.COCOA, 4)
478    *           .addCopies(Bean.GARDEN, 6)
479    *           .addCopies(Bean.RED, 8)
480    *           .addCopies(Bean.BLACK_EYED, 10)
481    *           .build();}</pre>
482    *
483    * <p>Builder instances can be reused; it is safe to call {@link #build} multiple
484    * times to build multiple multisets in series.
485    *
486    * @since 2.0
487    */
488   public static class Builder<E> extends ImmutableCollection.Builder<E> {
489     final Multiset<E> contents;
490 
491     /**
492      * Creates a new builder. The returned builder is equivalent to the builder
493      * generated by {@link ImmutableMultiset#builder}.
494      */
495     public Builder() {
496       this(LinkedHashMultiset.<E>create());
497     }
498 
499     Builder(Multiset<E> contents) {
500       this.contents = contents;
501     }
502 
503     /**
504      * Adds {@code element} to the {@code ImmutableMultiset}.
505      *
506      * @param element the element to add
507      * @return this {@code Builder} object
508      * @throws NullPointerException if {@code element} is null
509      */
510     @CanIgnoreReturnValue
511     @Override
512     public Builder<E> add(E element) {
513       contents.add(checkNotNull(element));
514       return this;
515     }
516 
517     /**
518      * Adds a number of occurrences of an element to this {@code
519      * ImmutableMultiset}.
520      *
521      * @param element the element to add
522      * @param occurrences the number of occurrences of the element to add. May
523      *     be zero, in which case no change will be made.
524      * @return this {@code Builder} object
525      * @throws NullPointerException if {@code element} is null
526      * @throws IllegalArgumentException if {@code occurrences} is negative, or
527      *     if this operation would result in more than {@link Integer#MAX_VALUE}
528      *     occurrences of the element
529      */
530     @CanIgnoreReturnValue
531     public Builder<E> addCopies(E element, int occurrences) {
532       contents.add(checkNotNull(element), occurrences);
533       return this;
534     }
535 
536     /**
537      * Adds or removes the necessary occurrences of an element such that the
538      * element attains the desired count.
539      *
540      * @param element the element to add or remove occurrences of
541      * @param count the desired count of the element in this multiset
542      * @return this {@code Builder} object
543      * @throws NullPointerException if {@code element} is null
544      * @throws IllegalArgumentException if {@code count} is negative
545      */
546     @CanIgnoreReturnValue
547     public Builder<E> setCount(E element, int count) {
548       contents.setCount(checkNotNull(element), count);
549       return this;
550     }
551 
552     /**
553      * Adds each element of {@code elements} to the {@code ImmutableMultiset}.
554      *
555      * @param elements the elements to add
556      * @return this {@code Builder} object
557      * @throws NullPointerException if {@code elements} is null or contains a
558      *     null element
559      */
560     @CanIgnoreReturnValue
561     @Override
562     public Builder<E> add(E... elements) {
563       super.add(elements);
564       return this;
565     }
566 
567     /**
568      * Adds each element of {@code elements} to the {@code ImmutableMultiset}.
569      *
570      * @param elements the {@code Iterable} to add to the {@code
571      *     ImmutableMultiset}
572      * @return this {@code Builder} object
573      * @throws NullPointerException if {@code elements} is null or contains a
574      *     null element
575      */
576     @CanIgnoreReturnValue
577     @Override
578     public Builder<E> addAll(Iterable<? extends E> elements) {
579       if (elements instanceof Multiset) {
580         Multiset<? extends E> multiset = Multisets.cast(elements);
581         for (Entry<? extends E> entry : multiset.entrySet()) {
582           addCopies(entry.getElement(), entry.getCount());
583         }
584       } else {
585         super.addAll(elements);
586       }
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 to the {@code ImmutableMultiset}
594      * @return this {@code Builder} object
595      * @throws NullPointerException if {@code elements} is null or contains a
596      *     null element
597      */
598     @CanIgnoreReturnValue
599     @Override
600     public Builder<E> addAll(Iterator<? extends E> elements) {
601       super.addAll(elements);
602       return this;
603     }
604 
605     /**
606      * Returns a newly-created {@code ImmutableMultiset} based on the contents
607      * of the {@code Builder}.
608      */
609     @Override
610     public ImmutableMultiset<E> build() {
611       return copyOf(contents);
612     }
613   }
614 }