View Javadoc
1   /*
2    * Copyright (C) 2011 The Guava Authors
3    *
4    * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
5    * in compliance with the License. You may obtain a copy of the License at
6    *
7    * http://www.apache.org/licenses/LICENSE-2.0
8    *
9    * Unless required by applicable law or agreed to in writing, software distributed under the
10   * License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either
11   * express or implied. See the License for the specific language governing permissions and
12   * limitations under the License.
13   */
14  
15  package com.google.common.collect;
16  
17  import static com.google.common.base.Preconditions.checkArgument;
18  import static com.google.common.base.Preconditions.checkNotNull;
19  
20  import com.google.common.annotations.Beta;
21  import com.google.common.annotations.GwtIncompatible;
22  import com.google.errorprone.annotations.CanIgnoreReturnValue;
23  import com.google.errorprone.annotations.concurrent.LazyInit;
24  import java.io.Serializable;
25  import java.util.Arrays;
26  import java.util.Collection;
27  import java.util.Collections;
28  import java.util.Comparator;
29  import java.util.Iterator;
30  import java.util.List;
31  import java.util.function.Function;
32  import java.util.function.ToIntFunction;
33  import java.util.stream.Collector;
34  
35  /**
36   * A {@link SortedMultiset} whose contents will never change, with many other important properties
37   * detailed at {@link ImmutableCollection}.
38   *
39   * <p><b>Warning:</b> as with any sorted collection, you are strongly advised not to use a {@link
40   * Comparator} or {@link Comparable} type whose comparison behavior is <i>inconsistent with
41   * equals</i>. That is, {@code a.compareTo(b)} or {@code comparator.compare(a, b)} should equal zero
42   * <i>if and only if</i> {@code a.equals(b)}. If this advice is not followed, the resulting
43   * collection will not correctly obey its specification.
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 Louis Wasserman
50   * @since 12.0
51   */
52  @GwtIncompatible // hasn't been tested yet
53  public abstract class ImmutableSortedMultiset<E> extends ImmutableSortedMultisetFauxverideShim<E>
54      implements SortedMultiset<E> {
55    // TODO(lowasser): GWT compatibility
56  
57    /**
58     * Returns a {@code Collector} that accumulates the input elements into a new
59     * {@code ImmutableMultiset}.  Elements are sorted by the specified comparator.
60     *
61     * <p><b>Warning:</b> {@code comparator} should be <i>consistent with {@code
62     * equals}</i> as explained in the {@link Comparator} documentation.
63     *
64     * @since 21.0
65     */
66    @Beta
67    public static <E> Collector<E, ?, ImmutableSortedMultiset<E>> toImmutableSortedMultiset(
68        Comparator<? super E> comparator) {
69      return toImmutableSortedMultiset(comparator, Function.identity(), e -> 1);
70    }
71  
72    /**
73     * Returns a {@code Collector} that accumulates elements into an {@code ImmutableSortedMultiset}
74     * whose elements are the result of applying {@code elementFunction} to the inputs, with counts
75     * equal to the result of applying {@code countFunction} to the inputs.
76     *
77     * <p>If the mapped elements contain duplicates (according to {@code comparator}), the first
78     * occurrence in encounter order appears in the resulting multiset, with count equal to the sum of
79     * the outputs of {@code countFunction.applyAsInt(t)} for each {@code t} mapped to that element.
80     *
81     * @since 22.0
82     */
83    public static <T, E> Collector<T, ?, ImmutableSortedMultiset<E>> toImmutableSortedMultiset(
84        Comparator<? super E> comparator,
85        Function<? super T, ? extends E> elementFunction,
86        ToIntFunction<? super T> countFunction) {
87      checkNotNull(comparator);
88      checkNotNull(elementFunction);
89      checkNotNull(countFunction);
90      return Collector.of(
91          () -> TreeMultiset.create(comparator),
92          (multiset, t) ->
93              multiset.add(checkNotNull(elementFunction.apply(t)), countFunction.applyAsInt(t)),
94          (multiset1, multiset2) -> {
95            multiset1.addAll(multiset2);
96            return multiset1;
97          },
98          (Multiset<E> multiset) -> copyOfSortedEntries(comparator, multiset.entrySet()));
99    }
100 
101   /**
102    * Returns the empty immutable sorted multiset.
103    */
104   @SuppressWarnings("unchecked")
105   public static <E> ImmutableSortedMultiset<E> of() {
106     return (ImmutableSortedMultiset) RegularImmutableSortedMultiset.NATURAL_EMPTY_MULTISET;
107   }
108 
109   /**
110    * Returns an immutable sorted multiset containing a single element.
111    */
112   public static <E extends Comparable<? super E>> ImmutableSortedMultiset<E> of(E element) {
113     RegularImmutableSortedSet<E> elementSet =
114         (RegularImmutableSortedSet<E>) ImmutableSortedSet.of(element);
115     long[] cumulativeCounts = {0, 1};
116     return new RegularImmutableSortedMultiset<E>(elementSet, cumulativeCounts, 0, 1);
117   }
118 
119   /**
120    * Returns an immutable sorted multiset containing the given elements sorted by their natural
121    * ordering.
122    *
123    * @throws NullPointerException if any element is null
124    */
125   @SuppressWarnings("unchecked")
126   public static <E extends Comparable<? super E>> ImmutableSortedMultiset<E> of(E e1, E e2) {
127     return copyOf(Ordering.natural(), Arrays.asList(e1, e2));
128   }
129 
130   /**
131    * Returns an immutable sorted multiset containing the given elements sorted by their natural
132    * ordering.
133    *
134    * @throws NullPointerException if any element is null
135    */
136   @SuppressWarnings("unchecked")
137   public static <E extends Comparable<? super E>> ImmutableSortedMultiset<E> of(E e1, E e2, E e3) {
138     return copyOf(Ordering.natural(), Arrays.asList(e1, e2, e3));
139   }
140 
141   /**
142    * Returns an immutable sorted multiset containing the given elements sorted by their natural
143    * ordering.
144    *
145    * @throws NullPointerException if any element is null
146    */
147   @SuppressWarnings("unchecked")
148   public static <E extends Comparable<? super E>> ImmutableSortedMultiset<E> of(
149       E e1, E e2, E e3, E e4) {
150     return copyOf(Ordering.natural(), Arrays.asList(e1, e2, e3, e4));
151   }
152 
153   /**
154    * Returns an immutable sorted multiset containing the given elements sorted by their natural
155    * ordering.
156    *
157    * @throws NullPointerException if any element is null
158    */
159   @SuppressWarnings("unchecked")
160   public static <E extends Comparable<? super E>> ImmutableSortedMultiset<E> of(
161       E e1, E e2, E e3, E e4, E e5) {
162     return copyOf(Ordering.natural(), Arrays.asList(e1, e2, e3, e4, e5));
163   }
164 
165   /**
166    * Returns an immutable sorted multiset containing the given elements sorted by their natural
167    * ordering.
168    *
169    * @throws NullPointerException if any element is null
170    */
171   @SuppressWarnings("unchecked")
172   public static <E extends Comparable<? super E>> ImmutableSortedMultiset<E> of(
173       E e1, E e2, E e3, E e4, E e5, E e6, E... remaining) {
174     int size = remaining.length + 6;
175     List<E> all = Lists.newArrayListWithCapacity(size);
176     Collections.addAll(all, e1, e2, e3, e4, e5, e6);
177     Collections.addAll(all, remaining);
178     return copyOf(Ordering.natural(), all);
179   }
180 
181   /**
182    * Returns an immutable sorted multiset containing the given elements sorted by their natural
183    * ordering.
184    *
185    * @throws NullPointerException if any of {@code elements} is null
186    */
187   public static <E extends Comparable<? super E>> ImmutableSortedMultiset<E> copyOf(E[] elements) {
188     return copyOf(Ordering.natural(), Arrays.asList(elements));
189   }
190 
191   /**
192    * Returns an immutable sorted multiset containing the given elements sorted by their natural
193    * ordering. To create a copy of a {@code SortedMultiset} that preserves the
194    * comparator, call {@link #copyOfSorted} instead. This method iterates over {@code elements} at
195    * most once.
196    *
197    * <p>Note that if {@code s} is a {@code Multiset<String>}, then {@code
198    * ImmutableSortedMultiset.copyOf(s)} returns an {@code ImmutableSortedMultiset<String>}
199    * containing each of the strings in {@code s}, while {@code ImmutableSortedMultiset.of(s)}
200    * returns an {@code ImmutableSortedMultiset<Multiset<String>>} containing one element (the given
201    * multiset itself).
202    *
203    * <p>Despite the method name, this method attempts to avoid actually copying the data when it is
204    * safe to do so. The exact circumstances under which a copy will or will not be performed are
205    * undocumented and subject to change.
206    *
207    * <p>This method is not type-safe, as it may be called on elements that are not mutually
208    * comparable.
209    *
210    * @throws ClassCastException if the elements are not mutually comparable
211    * @throws NullPointerException if any of {@code elements} is null
212    */
213   public static <E> ImmutableSortedMultiset<E> copyOf(Iterable<? extends E> elements) {
214     // Hack around E not being a subtype of Comparable.
215     // Unsafe, see ImmutableSortedMultisetFauxverideShim.
216     @SuppressWarnings("unchecked")
217     Ordering<E> naturalOrder = (Ordering<E>) Ordering.<Comparable>natural();
218     return copyOf(naturalOrder, elements);
219   }
220 
221   /**
222    * Returns an immutable sorted multiset containing the given elements sorted by their natural
223    * ordering.
224    *
225    * <p>This method is not type-safe, as it may be called on elements that are not mutually
226    * comparable.
227    *
228    * @throws ClassCastException if the elements are not mutually comparable
229    * @throws NullPointerException if any of {@code elements} is null
230    */
231   public static <E> ImmutableSortedMultiset<E> copyOf(Iterator<? extends E> elements) {
232     // Hack around E not being a subtype of Comparable.
233     // Unsafe, see ImmutableSortedMultisetFauxverideShim.
234     @SuppressWarnings("unchecked")
235     Ordering<E> naturalOrder = (Ordering<E>) Ordering.<Comparable>natural();
236     return copyOf(naturalOrder, elements);
237   }
238 
239   /**
240    * Returns an immutable sorted multiset containing the given elements sorted by the given {@code
241    * Comparator}.
242    *
243    * @throws NullPointerException if {@code comparator} or any of {@code elements} is null
244    */
245   public static <E> ImmutableSortedMultiset<E> copyOf(
246       Comparator<? super E> comparator, Iterator<? extends E> elements) {
247     checkNotNull(comparator);
248     return new Builder<E>(comparator).addAll(elements).build();
249   }
250 
251   /**
252    * Returns an immutable sorted multiset containing the given elements sorted by the given {@code
253    * Comparator}. This method iterates over {@code elements} at most once.
254    *
255    * <p>Despite the method name, this method attempts to avoid actually copying the data when it is
256    * safe to do so. The exact circumstances under which a copy will or will not be performed are
257    * undocumented and subject to change.
258    *
259    * @throws NullPointerException if {@code comparator} or any of {@code elements} is null
260    */
261   public static <E> ImmutableSortedMultiset<E> copyOf(
262       Comparator<? super E> comparator, Iterable<? extends E> elements) {
263     if (elements instanceof ImmutableSortedMultiset) {
264       @SuppressWarnings("unchecked") // immutable collections are always safe for covariant casts
265       ImmutableSortedMultiset<E> multiset = (ImmutableSortedMultiset<E>) elements;
266       if (comparator.equals(multiset.comparator())) {
267         if (multiset.isPartialView()) {
268           return copyOfSortedEntries(comparator, multiset.entrySet().asList());
269         } else {
270           return multiset;
271         }
272       }
273     }
274     elements = Lists.newArrayList(elements); // defensive copy
275     TreeMultiset<E> sortedCopy = TreeMultiset.create(checkNotNull(comparator));
276     Iterables.addAll(sortedCopy, elements);
277     return copyOfSortedEntries(comparator, sortedCopy.entrySet());
278   }
279 
280   /**
281    * Returns an immutable sorted multiset containing the elements of a sorted multiset, sorted by
282    * the same {@code Comparator}. That behavior differs from {@link #copyOf(Iterable)}, which
283    * always uses the natural ordering of the elements.
284    *
285    * <p>Despite the method name, this method attempts to avoid actually copying the data when it is
286    * safe to do so. The exact circumstances under which a copy will or will not be performed are
287    * undocumented and subject to change.
288    *
289    * <p>This method is safe to use even when {@code sortedMultiset} is a synchronized or concurrent
290    * collection that is currently being modified by another thread.
291    *
292    * @throws NullPointerException if {@code sortedMultiset} or any of its elements is null
293    */
294   public static <E> ImmutableSortedMultiset<E> copyOfSorted(SortedMultiset<E> sortedMultiset) {
295     return copyOfSortedEntries(
296         sortedMultiset.comparator(), Lists.newArrayList(sortedMultiset.entrySet()));
297   }
298 
299   private static <E> ImmutableSortedMultiset<E> copyOfSortedEntries(
300       Comparator<? super E> comparator, Collection<Entry<E>> entries) {
301     if (entries.isEmpty()) {
302       return emptyMultiset(comparator);
303     }
304     ImmutableList.Builder<E> elementsBuilder = new ImmutableList.Builder<E>(entries.size());
305     long[] cumulativeCounts = new long[entries.size() + 1];
306     int i = 0;
307     for (Entry<E> entry : entries) {
308       elementsBuilder.add(entry.getElement());
309       cumulativeCounts[i + 1] = cumulativeCounts[i] + entry.getCount();
310       i++;
311     }
312     return new RegularImmutableSortedMultiset<E>(
313         new RegularImmutableSortedSet<E>(elementsBuilder.build(), comparator),
314         cumulativeCounts,
315         0,
316         entries.size());
317   }
318 
319   @SuppressWarnings("unchecked")
320   static <E> ImmutableSortedMultiset<E> emptyMultiset(Comparator<? super E> comparator) {
321     if (Ordering.natural().equals(comparator)) {
322       return (ImmutableSortedMultiset<E>) RegularImmutableSortedMultiset.NATURAL_EMPTY_MULTISET;
323     } else {
324       return new RegularImmutableSortedMultiset<E>(comparator);
325     }
326   }
327 
328   ImmutableSortedMultiset() {}
329 
330   @Override
331   public final Comparator<? super E> comparator() {
332     return elementSet().comparator();
333   }
334 
335   @Override
336   public abstract ImmutableSortedSet<E> elementSet();
337 
338   @LazyInit
339   transient ImmutableSortedMultiset<E> descendingMultiset;
340 
341   @Override
342   public ImmutableSortedMultiset<E> descendingMultiset() {
343     ImmutableSortedMultiset<E> result = descendingMultiset;
344     if (result == null) {
345       return descendingMultiset =
346           this.isEmpty()
347               ? emptyMultiset(Ordering.from(comparator()).reverse())
348               : new DescendingImmutableSortedMultiset<E>(this);
349     }
350     return result;
351   }
352 
353   /**
354    * {@inheritDoc}
355    *
356    * <p>This implementation is guaranteed to throw an {@link UnsupportedOperationException}.
357    *
358    * @throws UnsupportedOperationException always
359    * @deprecated Unsupported operation.
360    */
361   @CanIgnoreReturnValue
362   @Deprecated
363   @Override
364   public final Entry<E> pollFirstEntry() {
365     throw new UnsupportedOperationException();
366   }
367 
368   /**
369    * {@inheritDoc}
370    *
371    * <p>This implementation is guaranteed to throw an {@link UnsupportedOperationException}.
372    *
373    * @throws UnsupportedOperationException always
374    * @deprecated Unsupported operation.
375    */
376   @CanIgnoreReturnValue
377   @Deprecated
378   @Override
379   public final Entry<E> pollLastEntry() {
380     throw new UnsupportedOperationException();
381   }
382 
383   @Override
384   public abstract ImmutableSortedMultiset<E> headMultiset(E upperBound, BoundType boundType);
385 
386   @Override
387   public ImmutableSortedMultiset<E> subMultiset(
388       E lowerBound, BoundType lowerBoundType, E upperBound, BoundType upperBoundType) {
389     checkArgument(
390         comparator().compare(lowerBound, upperBound) <= 0,
391         "Expected lowerBound <= upperBound but %s > %s",
392         lowerBound,
393         upperBound);
394     return tailMultiset(lowerBound, lowerBoundType).headMultiset(upperBound, upperBoundType);
395   }
396 
397   @Override
398   public abstract ImmutableSortedMultiset<E> tailMultiset(E lowerBound, BoundType boundType);
399 
400   /**
401    * Returns a builder that creates immutable sorted multisets with an explicit comparator. If the
402    * comparator has a more general type than the set being generated, such as creating a {@code
403    * SortedMultiset<Integer>} with a {@code Comparator<Number>}, use the {@link Builder}
404    * constructor instead.
405    *
406    * @throws NullPointerException if {@code comparator} is null
407    */
408   public static <E> Builder<E> orderedBy(Comparator<E> comparator) {
409     return new Builder<E>(comparator);
410   }
411 
412   /**
413    * Returns a builder that creates immutable sorted multisets whose elements are ordered by the
414    * reverse of their natural ordering.
415    *
416    * <p>Note: the type parameter {@code E} extends {@code Comparable<?>} rather than {@code
417    * Comparable<? super E>} as a workaround for javac <a
418    * href="http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6468354">bug 6468354</a>.
419    */
420   public static <E extends Comparable<?>> Builder<E> reverseOrder() {
421     return new Builder<E>(Ordering.natural().reverse());
422   }
423 
424   /**
425    * Returns a builder that creates immutable sorted multisets whose elements are ordered by their
426    * natural ordering. The sorted multisets use {@link Ordering#natural()} as the comparator. This
427    * method provides more type-safety than {@link #builder}, as it can be called only for classes
428    * that implement {@link Comparable}.
429    *
430    * <p>Note: the type parameter {@code E} extends {@code Comparable<?>} rather than {@code
431    * Comparable<? super E>} as a workaround for javac <a
432    * href="http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6468354">bug 6468354</a>.
433    */
434   public static <E extends Comparable<?>> Builder<E> naturalOrder() {
435     return new Builder<E>(Ordering.natural());
436   }
437 
438   /**
439    * A builder for creating immutable multiset instances, especially {@code public static final}
440    * multisets ("constant multisets"). Example:
441    *
442    * <pre> {@code
443    *
444    *   public static final ImmutableSortedMultiset<Bean> BEANS =
445    *       new ImmutableSortedMultiset.Builder<Bean>(colorComparator())
446    *           .addCopies(Bean.COCOA, 4)
447    *           .addCopies(Bean.GARDEN, 6)
448    *           .addCopies(Bean.RED, 8)
449    *           .addCopies(Bean.BLACK_EYED, 10)
450    *           .build();}</pre>
451    *
452    * <p>Builder instances can be reused; it is safe to call {@link #build} multiple times to build
453    * multiple multisets in series.
454    *
455    * @since 12.0
456    */
457   public static class Builder<E> extends ImmutableMultiset.Builder<E> {
458     /**
459      * Creates a new builder. The returned builder is equivalent to the builder generated by
460      * {@link ImmutableSortedMultiset#orderedBy(Comparator)}.
461      */
462     public Builder(Comparator<? super E> comparator) {
463       super(TreeMultiset.<E>create(checkNotNull(comparator)));
464     }
465 
466     /**
467      * Adds {@code element} to the {@code ImmutableSortedMultiset}.
468      *
469      * @param element the element to add
470      * @return this {@code Builder} object
471      * @throws NullPointerException if {@code element} is null
472      */
473     @CanIgnoreReturnValue
474     @Override
475     public Builder<E> add(E element) {
476       super.add(element);
477       return this;
478     }
479 
480     /**
481      * Adds a number of occurrences of an element to this {@code ImmutableSortedMultiset}.
482      *
483      * @param element the element to add
484      * @param occurrences the number of occurrences of the element to add. May be zero, in which
485      *        case no change will be made.
486      * @return this {@code Builder} object
487      * @throws NullPointerException if {@code element} is null
488      * @throws IllegalArgumentException if {@code occurrences} is negative, or if this operation
489      *         would result in more than {@link Integer#MAX_VALUE} occurrences of the element
490      */
491     @CanIgnoreReturnValue
492     @Override
493     public Builder<E> addCopies(E element, int occurrences) {
494       super.addCopies(element, occurrences);
495       return this;
496     }
497 
498     /**
499      * Adds or removes the necessary occurrences of an element such that the element attains the
500      * desired count.
501      *
502      * @param element the element to add or remove occurrences of
503      * @param count the desired count of the element in this multiset
504      * @return this {@code Builder} object
505      * @throws NullPointerException if {@code element} is null
506      * @throws IllegalArgumentException if {@code count} is negative
507      */
508     @CanIgnoreReturnValue
509     @Override
510     public Builder<E> setCount(E element, int count) {
511       super.setCount(element, count);
512       return this;
513     }
514 
515     /**
516      * Adds each element of {@code elements} to the {@code ImmutableSortedMultiset}.
517      *
518      * @param elements the elements to add
519      * @return this {@code Builder} object
520      * @throws NullPointerException if {@code elements} is null or contains a null element
521      */
522     @CanIgnoreReturnValue
523     @Override
524     public Builder<E> add(E... elements) {
525       super.add(elements);
526       return this;
527     }
528 
529     /**
530      * Adds each element of {@code elements} to the {@code ImmutableSortedMultiset}.
531      *
532      * @param elements the {@code Iterable} to add to the {@code ImmutableSortedMultiset}
533      * @return this {@code Builder} object
534      * @throws NullPointerException if {@code elements} is null or contains a null element
535      */
536     @CanIgnoreReturnValue
537     @Override
538     public Builder<E> addAll(Iterable<? extends E> elements) {
539       super.addAll(elements);
540       return this;
541     }
542 
543     /**
544      * Adds each element of {@code elements} to the {@code ImmutableSortedMultiset}.
545      *
546      * @param elements the elements to add to the {@code ImmutableSortedMultiset}
547      * @return this {@code Builder} object
548      * @throws NullPointerException if {@code elements} is null or contains a null element
549      */
550     @CanIgnoreReturnValue
551     @Override
552     public Builder<E> addAll(Iterator<? extends E> elements) {
553       super.addAll(elements);
554       return this;
555     }
556 
557     /**
558      * Returns a newly-created {@code ImmutableSortedMultiset} based on the contents of the {@code
559      * Builder}.
560      */
561     @Override
562     public ImmutableSortedMultiset<E> build() {
563       return copyOfSorted((SortedMultiset<E>) contents);
564     }
565   }
566 
567   private static final class SerializedForm<E> implements Serializable {
568     final Comparator<? super E> comparator;
569     final E[] elements;
570     final int[] counts;
571 
572     @SuppressWarnings("unchecked")
573     SerializedForm(SortedMultiset<E> multiset) {
574       this.comparator = multiset.comparator();
575       int n = multiset.entrySet().size();
576       elements = (E[]) new Object[n];
577       counts = new int[n];
578       int i = 0;
579       for (Entry<E> entry : multiset.entrySet()) {
580         elements[i] = entry.getElement();
581         counts[i] = entry.getCount();
582         i++;
583       }
584     }
585 
586     Object readResolve() {
587       int n = elements.length;
588       Builder<E> builder = new Builder<>(comparator);
589       for (int i = 0; i < n; i++) {
590         builder.addCopies(elements[i], counts[i]);
591       }
592       return builder.build();
593     }
594   }
595 
596   @Override
597   Object writeReplace() {
598     return new SerializedForm<E>(this);
599   }
600 }