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