001/*
002 * Copyright (C) 2011 The Guava Authors
003 *
004 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
005 * in compliance with the License. You may obtain a copy of the License at
006 *
007 * http://www.apache.org/licenses/LICENSE-2.0
008 *
009 * Unless required by applicable law or agreed to in writing, software distributed under the
010 * License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either
011 * express or implied. See the License for the specific language governing permissions and
012 * limitations under the License.
013 */
014
015package com.google.common.collect;
016
017import static com.google.common.base.Preconditions.checkArgument;
018import static com.google.common.base.Preconditions.checkNotNull;
019
020import com.google.common.annotations.GwtIncompatible;
021import com.google.common.annotations.J2ktIncompatible;
022import com.google.errorprone.annotations.CanIgnoreReturnValue;
023import com.google.errorprone.annotations.DoNotCall;
024import com.google.errorprone.annotations.concurrent.LazyInit;
025import java.io.InvalidObjectException;
026import java.io.ObjectInputStream;
027import java.io.Serializable;
028import java.util.Arrays;
029import java.util.Collection;
030import java.util.Collections;
031import java.util.Comparator;
032import java.util.Iterator;
033import java.util.List;
034import java.util.function.Function;
035import java.util.function.ToIntFunction;
036import java.util.stream.Collector;
037import javax.annotation.CheckForNull;
038import org.checkerframework.checker.nullness.qual.Nullable;
039
040/**
041 * A {@link SortedMultiset} whose contents will never change, with many other important properties
042 * detailed at {@link ImmutableCollection}.
043 *
044 * <p><b>Warning:</b> as with any sorted collection, you are strongly advised not to use a {@link
045 * Comparator} or {@link Comparable} type whose comparison behavior is <i>inconsistent with
046 * equals</i>. That is, {@code a.compareTo(b)} or {@code comparator.compare(a, b)} should equal zero
047 * <i>if and only if</i> {@code a.equals(b)}. If this advice is not followed, the resulting
048 * collection will not correctly obey its specification.
049 *
050 * <p>See the Guava User Guide article on <a href=
051 * "https://github.com/google/guava/wiki/ImmutableCollectionsExplained">immutable collections</a>.
052 *
053 * @author Louis Wasserman
054 * @since 12.0
055 */
056@GwtIncompatible // hasn't been tested yet
057@ElementTypesAreNonnullByDefault
058public abstract class ImmutableSortedMultiset<E> extends ImmutableSortedMultisetFauxverideShim<E>
059    implements SortedMultiset<E> {
060  // TODO(lowasser): GWT compatibility
061
062  /**
063   * Returns a {@code Collector} that accumulates the input elements into a new {@code
064   * ImmutableMultiset}. Elements are sorted by the specified comparator.
065   *
066   * <p><b>Warning:</b> {@code comparator} should be <i>consistent with {@code equals}</i> as
067   * explained in the {@link Comparator} documentation.
068   *
069   * @since 21.0
070   */
071  public static <E> Collector<E, ?, ImmutableSortedMultiset<E>> toImmutableSortedMultiset(
072      Comparator<? super E> comparator) {
073    return toImmutableSortedMultiset(comparator, Function.identity(), e -> 1);
074  }
075
076  /**
077   * Returns a {@code Collector} that accumulates elements into an {@code ImmutableSortedMultiset}
078   * whose elements are the result of applying {@code elementFunction} to the inputs, with counts
079   * equal to the result of applying {@code countFunction} to the inputs.
080   *
081   * <p>If the mapped elements contain duplicates (according to {@code comparator}), the first
082   * occurrence in encounter order appears in the resulting multiset, with count equal to the sum of
083   * the outputs of {@code countFunction.applyAsInt(t)} for each {@code t} mapped to that element.
084   *
085   * @since 22.0
086   */
087  public static <T extends @Nullable Object, E>
088      Collector<T, ?, ImmutableSortedMultiset<E>> toImmutableSortedMultiset(
089          Comparator<? super E> comparator,
090          Function<? super T, ? extends E> elementFunction,
091          ToIntFunction<? super T> countFunction) {
092    checkNotNull(comparator);
093    checkNotNull(elementFunction);
094    checkNotNull(countFunction);
095    return Collector.of(
096        () -> TreeMultiset.create(comparator),
097        (multiset, t) ->
098            multiset.add(checkNotNull(elementFunction.apply(t)), countFunction.applyAsInt(t)),
099        (multiset1, multiset2) -> {
100          multiset1.addAll(multiset2);
101          return multiset1;
102        },
103        (Multiset<E> multiset) -> copyOfSortedEntries(comparator, multiset.entrySet()));
104  }
105
106  /**
107   * Returns the empty immutable sorted multiset.
108   *
109   * <p><b>Performance note:</b> the instance returned is a singleton.
110   */
111  @SuppressWarnings("unchecked")
112  public static <E> ImmutableSortedMultiset<E> of() {
113    return (ImmutableSortedMultiset) RegularImmutableSortedMultiset.NATURAL_EMPTY_MULTISET;
114  }
115
116  /** Returns an immutable sorted multiset containing a single element. */
117  public static <E extends Comparable<? super E>> ImmutableSortedMultiset<E> of(E element) {
118    RegularImmutableSortedSet<E> elementSet =
119        (RegularImmutableSortedSet<E>) ImmutableSortedSet.of(element);
120    long[] cumulativeCounts = {0, 1};
121    return new RegularImmutableSortedMultiset<E>(elementSet, cumulativeCounts, 0, 1);
122  }
123
124  /**
125   * Returns an immutable sorted multiset containing the given elements sorted by their natural
126   * ordering.
127   *
128   * @throws NullPointerException if any element is null
129   */
130  public static <E extends Comparable<? super E>> ImmutableSortedMultiset<E> of(E e1, E e2) {
131    return copyOf(Ordering.natural(), Arrays.asList(e1, e2));
132  }
133
134  /**
135   * Returns an immutable sorted multiset containing the given elements sorted by their natural
136   * ordering.
137   *
138   * @throws NullPointerException if any element is null
139   */
140  public static <E extends Comparable<? super E>> ImmutableSortedMultiset<E> of(E e1, E e2, E e3) {
141    return copyOf(Ordering.natural(), Arrays.asList(e1, e2, e3));
142  }
143
144  /**
145   * Returns an immutable sorted multiset containing the given elements sorted by their natural
146   * ordering.
147   *
148   * @throws NullPointerException if any element is null
149   */
150  public static <E extends Comparable<? super E>> ImmutableSortedMultiset<E> of(
151      E e1, E e2, E e3, E e4) {
152    return copyOf(Ordering.natural(), Arrays.asList(e1, e2, e3, e4));
153  }
154
155  /**
156   * Returns an immutable sorted multiset containing the given elements sorted by their natural
157   * ordering.
158   *
159   * @throws NullPointerException if any element is null
160   */
161  public static <E extends Comparable<? super E>> ImmutableSortedMultiset<E> of(
162      E e1, E e2, E e3, E e4, E e5) {
163    return copyOf(Ordering.natural(), Arrays.asList(e1, e2, e3, e4, e5));
164  }
165
166  /**
167   * Returns an immutable sorted multiset containing the given elements sorted by their natural
168   * ordering.
169   *
170   * @throws NullPointerException if any element is null
171   */
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 comparator, call
194   * {@link #copyOfSorted} instead. This method iterates over {@code elements} at most once.
195   *
196   * <p>Note that if {@code s} is a {@code Multiset<String>}, then {@code
197   * ImmutableSortedMultiset.copyOf(s)} returns an {@code ImmutableSortedMultiset<String>}
198   * containing each of the strings in {@code s}, while {@code ImmutableSortedMultiset.of(s)}
199   * returns an {@code ImmutableSortedMultiset<Multiset<String>>} containing one element (the given
200   * multiset itself).
201   *
202   * <p>Despite the method name, this method attempts to avoid actually copying the data when it is
203   * safe to do so. The exact circumstances under which a copy will or will not be performed are
204   * undocumented and subject to change.
205   *
206   * <p>This method is not type-safe, as it may be called on elements that are not mutually
207   * comparable.
208   *
209   * @throws ClassCastException if the elements are not mutually comparable
210   * @throws NullPointerException if any of {@code elements} is null
211   */
212  public static <E> ImmutableSortedMultiset<E> copyOf(Iterable<? extends E> elements) {
213    // Hack around E not being a subtype of Comparable.
214    // Unsafe, see ImmutableSortedMultisetFauxverideShim.
215    @SuppressWarnings("unchecked")
216    Ordering<E> naturalOrder = (Ordering<E>) Ordering.<Comparable>natural();
217    return copyOf(naturalOrder, elements);
218  }
219
220  /**
221   * Returns an immutable sorted multiset containing the given elements sorted by their natural
222   * ordering.
223   *
224   * <p>This method is not type-safe, as it may be called on elements that are not mutually
225   * comparable.
226   *
227   * @throws ClassCastException if the elements are not mutually comparable
228   * @throws NullPointerException if any of {@code elements} is null
229   */
230  public static <E> ImmutableSortedMultiset<E> copyOf(Iterator<? extends E> elements) {
231    // Hack around E not being a subtype of Comparable.
232    // Unsafe, see ImmutableSortedMultisetFauxverideShim.
233    @SuppressWarnings("unchecked")
234    Ordering<E> naturalOrder = (Ordering<E>) Ordering.<Comparable>natural();
235    return copyOf(naturalOrder, elements);
236  }
237
238  /**
239   * Returns an immutable sorted multiset containing the given elements sorted by the given {@code
240   * Comparator}.
241   *
242   * @throws NullPointerException if {@code comparator} or any of {@code elements} is null
243   */
244  public static <E> ImmutableSortedMultiset<E> copyOf(
245      Comparator<? super E> comparator, Iterator<? extends E> elements) {
246    checkNotNull(comparator);
247    return new Builder<E>(comparator).addAll(elements).build();
248  }
249
250  /**
251   * Returns an immutable sorted multiset containing the given elements sorted by the given {@code
252   * Comparator}. This method iterates over {@code elements} at most once.
253   *
254   * <p>Despite the method name, this method attempts to avoid actually copying the data when it is
255   * safe to do so. The exact circumstances under which a copy will or will not be performed are
256   * undocumented and subject to change.
257   *
258   * @throws NullPointerException if {@code comparator} or any of {@code elements} is null
259   */
260  public static <E> ImmutableSortedMultiset<E> copyOf(
261      Comparator<? super E> comparator, Iterable<? extends E> elements) {
262    if (elements instanceof ImmutableSortedMultiset) {
263      @SuppressWarnings("unchecked") // immutable collections are always safe for covariant casts
264      ImmutableSortedMultiset<E> multiset = (ImmutableSortedMultiset<E>) elements;
265      if (comparator.equals(multiset.comparator())) {
266        if (multiset.isPartialView()) {
267          return copyOfSortedEntries(comparator, multiset.entrySet().asList());
268        } else {
269          return multiset;
270        }
271      }
272    }
273    elements = Lists.newArrayList(elements); // defensive copy
274    TreeMultiset<E> sortedCopy = TreeMultiset.create(checkNotNull(comparator));
275    Iterables.addAll(sortedCopy, elements);
276    return copyOfSortedEntries(comparator, sortedCopy.entrySet());
277  }
278
279  /**
280   * Returns an immutable sorted multiset containing the elements of a sorted multiset, sorted by
281   * the same {@code Comparator}. That behavior differs from {@link #copyOf(Iterable)}, which always
282   * uses the natural ordering of the elements.
283   *
284   * <p>Despite the method name, this method attempts to avoid actually copying the data when it is
285   * safe to do so. The exact circumstances under which a copy will or will not be performed are
286   * undocumented and subject to change.
287   *
288   * <p>This method is safe to use even when {@code sortedMultiset} is a synchronized or concurrent
289   * collection that is currently being modified by another thread.
290   *
291   * @throws NullPointerException if {@code sortedMultiset} or any of its elements is null
292   */
293  public static <E> ImmutableSortedMultiset<E> copyOfSorted(SortedMultiset<E> sortedMultiset) {
294    return copyOfSortedEntries(
295        sortedMultiset.comparator(), Lists.newArrayList(sortedMultiset.entrySet()));
296  }
297
298  private static <E> ImmutableSortedMultiset<E> copyOfSortedEntries(
299      Comparator<? super E> comparator, Collection<Entry<E>> entries) {
300    if (entries.isEmpty()) {
301      return emptyMultiset(comparator);
302    }
303    ImmutableList.Builder<E> elementsBuilder = new ImmutableList.Builder<E>(entries.size());
304    long[] cumulativeCounts = new long[entries.size() + 1];
305    int i = 0;
306    for (Entry<E> entry : entries) {
307      elementsBuilder.add(entry.getElement());
308      cumulativeCounts[i + 1] = cumulativeCounts[i] + entry.getCount();
309      i++;
310    }
311    return new RegularImmutableSortedMultiset<E>(
312        new RegularImmutableSortedSet<E>(elementsBuilder.build(), comparator),
313        cumulativeCounts,
314        0,
315        entries.size());
316  }
317
318  @SuppressWarnings("unchecked")
319  static <E> ImmutableSortedMultiset<E> emptyMultiset(Comparator<? super E> comparator) {
320    if (Ordering.natural().equals(comparator)) {
321      return (ImmutableSortedMultiset<E>) RegularImmutableSortedMultiset.NATURAL_EMPTY_MULTISET;
322    } else {
323      return new RegularImmutableSortedMultiset<E>(comparator);
324    }
325  }
326
327  ImmutableSortedMultiset() {}
328
329  @Override
330  public final Comparator<? super E> comparator() {
331    return elementSet().comparator();
332  }
333
334  @Override
335  public abstract ImmutableSortedSet<E> elementSet();
336
337  @LazyInit @CheckForNull transient ImmutableSortedMultiset<E> descendingMultiset;
338
339  @Override
340  public ImmutableSortedMultiset<E> descendingMultiset() {
341    ImmutableSortedMultiset<E> result = descendingMultiset;
342    if (result == null) {
343      return descendingMultiset =
344          this.isEmpty()
345              ? emptyMultiset(Ordering.from(comparator()).reverse())
346              : new DescendingImmutableSortedMultiset<E>(this);
347    }
348    return result;
349  }
350
351  /**
352   * {@inheritDoc}
353   *
354   * <p>This implementation is guaranteed to throw an {@link UnsupportedOperationException}.
355   *
356   * @throws UnsupportedOperationException always
357   * @deprecated Unsupported operation.
358   */
359  @CanIgnoreReturnValue
360  @Deprecated
361  @Override
362  @DoNotCall("Always throws UnsupportedOperationException")
363  @CheckForNull
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  @DoNotCall("Always throws UnsupportedOperationException")
380  @CheckForNull
381  public final Entry<E> pollLastEntry() {
382    throw new UnsupportedOperationException();
383  }
384
385  @Override
386  public abstract ImmutableSortedMultiset<E> headMultiset(E upperBound, BoundType boundType);
387
388  @Override
389  public ImmutableSortedMultiset<E> subMultiset(
390      E lowerBound, BoundType lowerBoundType, E upperBound, BoundType upperBoundType) {
391    checkArgument(
392        comparator().compare(lowerBound, upperBound) <= 0,
393        "Expected lowerBound <= upperBound but %s > %s",
394        lowerBound,
395        upperBound);
396    return tailMultiset(lowerBound, lowerBoundType).headMultiset(upperBound, upperBoundType);
397  }
398
399  @Override
400  public abstract ImmutableSortedMultiset<E> tailMultiset(E lowerBound, BoundType boundType);
401
402  /**
403   * Returns a builder that creates immutable sorted multisets with an explicit comparator. If the
404   * comparator has a more general type than the set being generated, such as creating a {@code
405   * SortedMultiset<Integer>} with a {@code Comparator<Number>}, use the {@link Builder} constructor
406   * instead.
407   *
408   * @throws NullPointerException if {@code comparator} is null
409   */
410  public static <E> Builder<E> orderedBy(Comparator<E> comparator) {
411    return new Builder<E>(comparator);
412  }
413
414  /**
415   * Returns a builder that creates immutable sorted multisets whose elements are ordered by the
416   * reverse of their natural ordering.
417   *
418   * <p>Note: the type parameter {@code E} extends {@code Comparable<?>} rather than {@code
419   * Comparable<? super E>} as a workaround for javac <a
420   * href="http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6468354">bug 6468354</a>.
421   */
422  public static <E extends Comparable<?>> Builder<E> reverseOrder() {
423    return new Builder<E>(Ordering.<E>natural().reverse());
424  }
425
426  /**
427   * Returns a builder that creates immutable sorted multisets whose elements are ordered by their
428   * natural ordering. The sorted multisets use {@link Ordering#natural()} as the comparator. This
429   * method provides more type-safety than {@link #builder}, as it can be called only for classes
430   * that implement {@link Comparable}.
431   *
432   * <p>Note: the type parameter {@code E} extends {@code Comparable<?>} rather than {@code
433   * Comparable<? super E>} as a workaround for javac <a
434   * href="http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6468354">bug 6468354</a>.
435   */
436  public static <E extends Comparable<?>> Builder<E> naturalOrder() {
437    return new Builder<E>(Ordering.natural());
438  }
439
440  /**
441   * A builder for creating immutable multiset instances, especially {@code public static final}
442   * multisets ("constant multisets"). Example:
443   *
444   * <pre>{@code
445   * public static final ImmutableSortedMultiset<Bean> BEANS =
446   *     new ImmutableSortedMultiset.Builder<Bean>(colorComparator())
447   *         .addCopies(Bean.COCOA, 4)
448   *         .addCopies(Bean.GARDEN, 6)
449   *         .addCopies(Bean.RED, 8)
450   *         .addCopies(Bean.BLACK_EYED, 10)
451   *         .build();
452   * }</pre>
453   *
454   * <p>Builder instances can be reused; it is safe to call {@link #build} multiple times to build
455   * multiple multisets in series.
456   *
457   * @since 12.0
458   */
459  public static class Builder<E> extends ImmutableMultiset.Builder<E> {
460    /**
461     * Creates a new builder. The returned builder is equivalent to the builder generated by {@link
462     * ImmutableSortedMultiset#orderedBy(Comparator)}.
463     */
464    public Builder(Comparator<? super E> comparator) {
465      super(TreeMultiset.<E>create(checkNotNull(comparator)));
466    }
467
468    /**
469     * Adds {@code element} to the {@code ImmutableSortedMultiset}.
470     *
471     * @param element the element to add
472     * @return this {@code Builder} object
473     * @throws NullPointerException if {@code element} is null
474     */
475    @CanIgnoreReturnValue
476    @Override
477    public Builder<E> add(E element) {
478      super.add(element);
479      return this;
480    }
481
482    /**
483     * Adds each element of {@code elements} to the {@code ImmutableSortedMultiset}.
484     *
485     * @param elements the elements to add
486     * @return this {@code Builder} object
487     * @throws NullPointerException if {@code elements} is null or contains a null element
488     */
489    @CanIgnoreReturnValue
490    @Override
491    public Builder<E> add(E... elements) {
492      super.add(elements);
493      return this;
494    }
495
496    /**
497     * Adds a number of occurrences of an element to this {@code ImmutableSortedMultiset}.
498     *
499     * @param element the element to add
500     * @param occurrences the number of occurrences of the element to add. May be zero, in which
501     *     case no change will be made.
502     * @return this {@code Builder} object
503     * @throws NullPointerException if {@code element} is null
504     * @throws IllegalArgumentException if {@code occurrences} is negative, or if this operation
505     *     would result in more than {@link Integer#MAX_VALUE} occurrences of the element
506     */
507    @CanIgnoreReturnValue
508    @Override
509    public Builder<E> addCopies(E element, int occurrences) {
510      super.addCopies(element, occurrences);
511      return this;
512    }
513
514    /**
515     * Adds or removes the necessary occurrences of an element such that the element attains the
516     * desired count.
517     *
518     * @param element the element to add or remove occurrences of
519     * @param count the desired count of the element in this multiset
520     * @return this {@code Builder} object
521     * @throws NullPointerException if {@code element} is null
522     * @throws IllegalArgumentException if {@code count} is negative
523     */
524    @CanIgnoreReturnValue
525    @Override
526    public Builder<E> setCount(E element, int count) {
527      super.setCount(element, count);
528      return this;
529    }
530
531    /**
532     * Adds each element of {@code elements} to the {@code ImmutableSortedMultiset}.
533     *
534     * @param elements the {@code Iterable} to add to the {@code ImmutableSortedMultiset}
535     * @return this {@code Builder} object
536     * @throws NullPointerException if {@code elements} is null or contains a null element
537     */
538    @CanIgnoreReturnValue
539    @Override
540    public Builder<E> addAll(Iterable<? extends E> elements) {
541      super.addAll(elements);
542      return this;
543    }
544
545    /**
546     * Adds each element of {@code elements} to the {@code ImmutableSortedMultiset}.
547     *
548     * @param elements the elements to add to the {@code ImmutableSortedMultiset}
549     * @return this {@code Builder} object
550     * @throws NullPointerException if {@code elements} is null or contains a null element
551     */
552    @CanIgnoreReturnValue
553    @Override
554    public Builder<E> addAll(Iterator<? extends E> elements) {
555      super.addAll(elements);
556      return this;
557    }
558
559    /**
560     * Returns a newly-created {@code ImmutableSortedMultiset} based on the contents of the {@code
561     * Builder}.
562     */
563    @Override
564    public ImmutableSortedMultiset<E> build() {
565      return copyOfSorted((SortedMultiset<E>) contents);
566    }
567  }
568
569  @J2ktIncompatible // serialization
570  private static final class SerializedForm<E> implements Serializable {
571    final Comparator<? super E> comparator;
572    final E[] elements;
573    final int[] counts;
574
575    @SuppressWarnings("unchecked")
576    SerializedForm(SortedMultiset<E> multiset) {
577      this.comparator = multiset.comparator();
578      int n = multiset.entrySet().size();
579      elements = (E[]) new Object[n];
580      counts = new int[n];
581      int i = 0;
582      for (Entry<E> entry : multiset.entrySet()) {
583        elements[i] = entry.getElement();
584        counts[i] = entry.getCount();
585        i++;
586      }
587    }
588
589    Object readResolve() {
590      int n = elements.length;
591      Builder<E> builder = new Builder<>(comparator);
592      for (int i = 0; i < n; i++) {
593        builder.addCopies(elements[i], counts[i]);
594      }
595      return builder.build();
596    }
597  }
598
599  @Override
600  @J2ktIncompatible // serialization
601  Object writeReplace() {
602    return new SerializedForm<E>(this);
603  }
604
605  @J2ktIncompatible // java.io.ObjectInputStream
606  private void readObject(ObjectInputStream stream) throws InvalidObjectException {
607    throw new InvalidObjectException("Use SerializedForm");
608  }
609}