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