Source code

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.common.annotations.J2ktIncompatible;
023import com.google.common.annotations.VisibleForTesting;
024import com.google.common.math.IntMath;
025import com.google.errorprone.annotations.CanIgnoreReturnValue;
026import com.google.errorprone.annotations.DoNotCall;
027import com.google.errorprone.annotations.concurrent.LazyInit;
028import java.io.InvalidObjectException;
029import java.io.ObjectInputStream;
030import java.io.Serializable;
031import java.util.Arrays;
032import java.util.Collection;
033import java.util.Collections;
034import java.util.Comparator;
035import java.util.Iterator;
036import java.util.List;
037import java.util.function.Function;
038import java.util.function.ToIntFunction;
039import java.util.stream.Collector;
040import javax.annotation.CheckForNull;
041import org.checkerframework.checker.nullness.qual.Nullable;
042
043/**
044 * A {@link SortedMultiset} whose contents will never change, with many other important properties
045 * detailed at {@link ImmutableCollection}.
046 *
047 * <p><b>Warning:</b> as with any sorted collection, you are strongly advised not to use a {@link
048 * Comparator} or {@link Comparable} type whose comparison behavior is <i>inconsistent with
049 * equals</i>. That is, {@code a.compareTo(b)} or {@code comparator.compare(a, b)} should equal zero
050 * <i>if and only if</i> {@code a.equals(b)}. If this advice is not followed, the resulting
051 * collection will not correctly obey its specification.
052 *
053 * <p>See the Guava User Guide article on <a href=
054 * "https://github.com/google/guava/wiki/ImmutableCollectionsExplained">immutable collections</a>.
055 *
056 * @author Louis Wasserman
057 * @since 12.0
058 */
059@GwtIncompatible // hasn't been tested yet
060@ElementTypesAreNonnullByDefault
061public abstract class ImmutableSortedMultiset<E> extends ImmutableMultiset<E>
062    implements SortedMultiset<E> {
063  // TODO(lowasser): GWT compatibility
064
065  /**
066   * Returns a {@code Collector} that accumulates the input elements into a new {@code
067   * ImmutableMultiset}. Elements are sorted by the specified comparator.
068   *
069   * <p><b>Warning:</b> {@code comparator} should be <i>consistent with {@code equals}</i> as
070   * explained in the {@link Comparator} documentation.
071   *
072   * @since 33.2.0 (available since 21.0 in guava-jre)
073   */
074  @SuppressWarnings({"AndroidJdkLibsChecker", "Java7ApiChecker"})
075  @IgnoreJRERequirement // Users will use this only if they're already using streams.
076  @Beta // TODO: b/288085449 - Remove.
077  public static <E> Collector<E, ?, ImmutableSortedMultiset<E>> toImmutableSortedMultiset(
078      Comparator<? super E> comparator) {
079    return toImmutableSortedMultiset(comparator, Function.identity(), e -> 1);
080  }
081
082  /**
083   * Returns a {@code Collector} that accumulates elements into an {@code ImmutableSortedMultiset}
084   * whose elements are the result of applying {@code elementFunction} to the inputs, with counts
085   * equal to the result of applying {@code countFunction} to the inputs.
086   *
087   * <p>If the mapped elements contain duplicates (according to {@code comparator}), the first
088   * occurrence in encounter order appears in the resulting multiset, with count equal to the sum of
089   * the outputs of {@code countFunction.applyAsInt(t)} for each {@code t} mapped to that element.
090   *
091   * @since 33.2.0 (available since 22.0 in guava-jre)
092   */
093  @SuppressWarnings({"AndroidJdkLibsChecker", "Java7ApiChecker"})
094  @IgnoreJRERequirement // Users will use this only if they're already using streams.
095  @Beta // TODO: b/288085449 - Remove.
096  public static <T extends @Nullable Object, E>
097      Collector<T, ?, ImmutableSortedMultiset<E>> toImmutableSortedMultiset(
098          Comparator<? super E> comparator,
099          Function<? super T, ? extends E> elementFunction,
100          ToIntFunction<? super T> countFunction) {
101    checkNotNull(comparator);
102    checkNotNull(elementFunction);
103    checkNotNull(countFunction);
104    return Collector.of(
105        () -> TreeMultiset.create(comparator),
106        (multiset, t) -> mapAndAdd(t, multiset, elementFunction, countFunction),
107        (multiset1, multiset2) -> {
108          multiset1.addAll(multiset2);
109          return multiset1;
110        },
111        (Multiset<E> multiset) -> copyOfSortedEntries(comparator, multiset.entrySet()));
112  }
113
114  @SuppressWarnings({"AndroidJdkLibsChecker", "Java7ApiChecker"})
115  @IgnoreJRERequirement // helper for toImmutableSortedMultiset
116  /*
117   * If we make these calls inline inside toImmutableSortedMultiset, we get an Animal Sniffer error,
118   * despite the @IgnoreJRERequirement annotation there. My assumption is that, because javac
119   * generates a synthetic method for the body of the lambda, the actual method calls that Animal
120   * Sniffer is flagging don't appear inside toImmutableSortedMultiset but rather inside that
121   * synthetic method. By moving those calls to a named method, we're able to apply
122   * @IgnoreJRERequirement somewhere that it will help.
123   */
124  private static <T extends @Nullable Object, E> void mapAndAdd(
125      T t,
126      Multiset<E> multiset,
127      Function<? super T, ? extends E> elementFunction,
128      ToIntFunction<? super T> countFunction) {
129    multiset.add(checkNotNull(elementFunction.apply(t)), countFunction.applyAsInt(t));
130  }
131
132  /**
133   * Returns the empty immutable sorted multiset.
134   *
135   * <p><b>Performance note:</b> the instance returned is a singleton.
136   */
137  @SuppressWarnings("unchecked")
138  public static <E> ImmutableSortedMultiset<E> of() {
139    return (ImmutableSortedMultiset) RegularImmutableSortedMultiset.NATURAL_EMPTY_MULTISET;
140  }
141
142  /** Returns an immutable sorted multiset containing a single element. */
143  public static <E extends Comparable<? super E>> ImmutableSortedMultiset<E> of(E element) {
144    RegularImmutableSortedSet<E> elementSet =
145        (RegularImmutableSortedSet<E>) ImmutableSortedSet.of(element);
146    long[] cumulativeCounts = {0, 1};
147    return new RegularImmutableSortedMultiset<>(elementSet, cumulativeCounts, 0, 1);
148  }
149
150  /**
151   * Returns an immutable sorted multiset containing the given elements sorted by their natural
152   * ordering.
153   *
154   * @throws NullPointerException if any element is null
155   */
156  public static <E extends Comparable<? super E>> ImmutableSortedMultiset<E> of(E e1, E e2) {
157    return copyOf(Ordering.natural(), Arrays.asList(e1, e2));
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  public static <E extends Comparable<? super E>> ImmutableSortedMultiset<E> of(E e1, E e2, E e3) {
167    return copyOf(Ordering.natural(), Arrays.asList(e1, e2, e3));
168  }
169
170  /**
171   * Returns an immutable sorted multiset containing the given elements sorted by their natural
172   * ordering.
173   *
174   * @throws NullPointerException if any element is null
175   */
176  public static <E extends Comparable<? super E>> ImmutableSortedMultiset<E> of(
177      E e1, E e2, E e3, E e4) {
178    return copyOf(Ordering.natural(), Arrays.asList(e1, e2, e3, e4));
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 element is null
186   */
187  public static <E extends Comparable<? super E>> ImmutableSortedMultiset<E> of(
188      E e1, E e2, E e3, E e4, E e5) {
189    return copyOf(Ordering.natural(), Arrays.asList(e1, e2, e3, e4, e5));
190  }
191
192  /**
193   * Returns an immutable sorted multiset containing the given elements sorted by their natural
194   * ordering.
195   *
196   * @throws NullPointerException if any element is null
197   */
198  public static <E extends Comparable<? super E>> ImmutableSortedMultiset<E> of(
199      E e1, E e2, E e3, E e4, E e5, E e6, E... remaining) {
200    int size = remaining.length + 6;
201    List<E> all = Lists.newArrayListWithCapacity(size);
202    Collections.addAll(all, e1, e2, e3, e4, e5, e6);
203    Collections.addAll(all, remaining);
204    return copyOf(Ordering.natural(), all);
205  }
206
207  /**
208   * Returns an immutable sorted multiset containing the given elements sorted by their natural
209   * ordering.
210   *
211   * @throws NullPointerException if any of {@code elements} is null
212   */
213  public static <E extends Comparable<? super E>> ImmutableSortedMultiset<E> copyOf(E[] elements) {
214    return copyOf(Ordering.natural(), Arrays.asList(elements));
215  }
216
217  /**
218   * Returns an immutable sorted multiset containing the given elements sorted by their natural
219   * ordering. To create a copy of a {@code SortedMultiset} that preserves the comparator, call
220   * {@link #copyOfSorted} instead. This method iterates over {@code elements} at most once.
221   *
222   * <p>Note that if {@code s} is a {@code Multiset<String>}, then {@code
223   * ImmutableSortedMultiset.copyOf(s)} returns an {@code ImmutableSortedMultiset<String>}
224   * containing each of the strings in {@code s}, while {@code ImmutableSortedMultiset.of(s)}
225   * returns an {@code ImmutableSortedMultiset<Multiset<String>>} containing one element (the given
226   * multiset itself).
227   *
228   * <p>Despite the method name, this method attempts to avoid actually copying the data when it is
229   * safe to do so. The exact circumstances under which a copy will or will not be performed are
230   * undocumented and subject to change.
231   *
232   * <p>This method is not type-safe, as it may be called on elements that are not mutually
233   * comparable.
234   *
235   * @throws ClassCastException if the elements are not mutually comparable
236   * @throws NullPointerException if any of {@code elements} is null
237   */
238  public static <E> ImmutableSortedMultiset<E> copyOf(Iterable<? extends E> elements) {
239    // Hack around E not being a subtype of Comparable.
240    // Unsafe, see ImmutableSortedMultisetFauxverideShim.
241    @SuppressWarnings("unchecked")
242    Ordering<E> naturalOrder = (Ordering<E>) Ordering.<Comparable<?>>natural();
243    return copyOf(naturalOrder, elements);
244  }
245
246  /**
247   * Returns an immutable sorted multiset containing the given elements sorted by their natural
248   * ordering.
249   *
250   * <p>This method is not type-safe, as it may be called on elements that are not mutually
251   * comparable.
252   *
253   * @throws ClassCastException if the elements are not mutually comparable
254   * @throws NullPointerException if any of {@code elements} is null
255   */
256  public static <E> ImmutableSortedMultiset<E> copyOf(Iterator<? extends E> elements) {
257    // Hack around E not being a subtype of Comparable.
258    // Unsafe, see ImmutableSortedMultisetFauxverideShim.
259    @SuppressWarnings("unchecked")
260    Ordering<E> naturalOrder = (Ordering<E>) Ordering.<Comparable<?>>natural();
261    return copyOf(naturalOrder, elements);
262  }
263
264  /**
265   * Returns an immutable sorted multiset containing the given elements sorted by the given {@code
266   * Comparator}.
267   *
268   * @throws NullPointerException if {@code comparator} or any of {@code elements} is null
269   */
270  public static <E> ImmutableSortedMultiset<E> copyOf(
271      Comparator<? super E> comparator, Iterator<? extends E> elements) {
272    checkNotNull(comparator);
273    return new Builder<E>(comparator).addAll(elements).build();
274  }
275
276  /**
277   * Returns an immutable sorted multiset containing the given elements sorted by the given {@code
278   * Comparator}. This method iterates over {@code elements} at most once.
279   *
280   * <p>Despite the method name, this method attempts to avoid actually copying the data when it is
281   * safe to do so. The exact circumstances under which a copy will or will not be performed are
282   * undocumented and subject to change.
283   *
284   * @throws NullPointerException if {@code comparator} or any of {@code elements} is null
285   */
286  public static <E> ImmutableSortedMultiset<E> copyOf(
287      Comparator<? super E> comparator, Iterable<? extends E> elements) {
288    if (elements instanceof ImmutableSortedMultiset) {
289      @SuppressWarnings("unchecked") // immutable collections are always safe for covariant casts
290      ImmutableSortedMultiset<E> multiset = (ImmutableSortedMultiset<E>) elements;
291      if (comparator.equals(multiset.comparator())) {
292        if (multiset.isPartialView()) {
293          return copyOfSortedEntries(comparator, multiset.entrySet().asList());
294        } else {
295          return multiset;
296        }
297      }
298    }
299    return new ImmutableSortedMultiset.Builder<E>(comparator).addAll(elements).build();
300  }
301
302  /**
303   * Returns an immutable sorted multiset containing the elements of a sorted multiset, sorted by
304   * the same {@code Comparator}. That behavior differs from {@link #copyOf(Iterable)}, which always
305   * uses the natural ordering of the elements.
306   *
307   * <p>Despite the method name, this method attempts to avoid actually copying the data when it is
308   * safe to do so. The exact circumstances under which a copy will or will not be performed are
309   * undocumented and subject to change.
310   *
311   * <p>This method is safe to use even when {@code sortedMultiset} is a synchronized or concurrent
312   * collection that is currently being modified by another thread.
313   *
314   * @throws NullPointerException if {@code sortedMultiset} or any of its elements is null
315   */
316  public static <E> ImmutableSortedMultiset<E> copyOfSorted(SortedMultiset<E> sortedMultiset) {
317    return copyOfSortedEntries(
318        sortedMultiset.comparator(), Lists.newArrayList(sortedMultiset.entrySet()));
319  }
320
321  private static <E> ImmutableSortedMultiset<E> copyOfSortedEntries(
322      Comparator<? super E> comparator, Collection<Entry<E>> entries) {
323    if (entries.isEmpty()) {
324      return emptyMultiset(comparator);
325    }
326    ImmutableList.Builder<E> elementsBuilder = new ImmutableList.Builder<>(entries.size());
327    long[] cumulativeCounts = new long[entries.size() + 1];
328    int i = 0;
329    for (Entry<E> entry : entries) {
330      elementsBuilder.add(entry.getElement());
331      cumulativeCounts[i + 1] = cumulativeCounts[i] + entry.getCount();
332      i++;
333    }
334    return new RegularImmutableSortedMultiset<>(
335        new RegularImmutableSortedSet<E>(elementsBuilder.build(), comparator),
336        cumulativeCounts,
337        0,
338        entries.size());
339  }
340
341  @SuppressWarnings("unchecked")
342  static <E> ImmutableSortedMultiset<E> emptyMultiset(Comparator<? super E> comparator) {
343    if (Ordering.natural().equals(comparator)) {
344      return (ImmutableSortedMultiset<E>) RegularImmutableSortedMultiset.NATURAL_EMPTY_MULTISET;
345    } else {
346      return new RegularImmutableSortedMultiset<>(comparator);
347    }
348  }
349
350  ImmutableSortedMultiset() {}
351
352  @Override
353  public final Comparator<? super E> comparator() {
354    return elementSet().comparator();
355  }
356
357  @Override
358  public abstract ImmutableSortedSet<E> elementSet();
359
360  @LazyInit @CheckForNull transient ImmutableSortedMultiset<E> descendingMultiset;
361
362  @Override
363  public ImmutableSortedMultiset<E> descendingMultiset() {
364    ImmutableSortedMultiset<E> result = descendingMultiset;
365    if (result == null) {
366      return descendingMultiset =
367          this.isEmpty()
368              ? emptyMultiset(Ordering.from(comparator()).reverse())
369              : new DescendingImmutableSortedMultiset<E>(this);
370    }
371    return result;
372  }
373
374  /**
375   * {@inheritDoc}
376   *
377   * <p>This implementation is guaranteed to throw an {@link UnsupportedOperationException}.
378   *
379   * @throws UnsupportedOperationException always
380   * @deprecated Unsupported operation.
381   */
382  @CanIgnoreReturnValue
383  @Deprecated
384  @Override
385  @DoNotCall("Always throws UnsupportedOperationException")
386  @CheckForNull
387  public final Entry<E> pollFirstEntry() {
388    throw new UnsupportedOperationException();
389  }
390
391  /**
392   * {@inheritDoc}
393   *
394   * <p>This implementation is guaranteed to throw an {@link UnsupportedOperationException}.
395   *
396   * @throws UnsupportedOperationException always
397   * @deprecated Unsupported operation.
398   */
399  @CanIgnoreReturnValue
400  @Deprecated
401  @Override
402  @DoNotCall("Always throws UnsupportedOperationException")
403  @CheckForNull
404  public final Entry<E> pollLastEntry() {
405    throw new UnsupportedOperationException();
406  }
407
408  @Override
409  public abstract ImmutableSortedMultiset<E> headMultiset(E upperBound, BoundType boundType);
410
411  @Override
412  public ImmutableSortedMultiset<E> subMultiset(
413      E lowerBound, BoundType lowerBoundType, E upperBound, BoundType upperBoundType) {
414    checkArgument(
415        comparator().compare(lowerBound, upperBound) <= 0,
416        "Expected lowerBound <= upperBound but %s > %s",
417        lowerBound,
418        upperBound);
419    return tailMultiset(lowerBound, lowerBoundType).headMultiset(upperBound, upperBoundType);
420  }
421
422  @Override
423  public abstract ImmutableSortedMultiset<E> tailMultiset(E lowerBound, BoundType boundType);
424
425  /**
426   * Returns a builder that creates immutable sorted multisets with an explicit comparator. If the
427   * comparator has a more general type than the set being generated, such as creating a {@code
428   * SortedMultiset<Integer>} with a {@code Comparator<Number>}, use the {@link Builder} constructor
429   * instead.
430   *
431   * @throws NullPointerException if {@code comparator} is null
432   */
433  public static <E> Builder<E> orderedBy(Comparator<E> comparator) {
434    return new Builder<>(comparator);
435  }
436
437  /**
438   * Returns a builder that creates immutable sorted multisets whose elements are ordered by the
439   * reverse of their natural ordering.
440   *
441   * <p>Note: the type parameter {@code E} extends {@code Comparable<?>} rather than {@code
442   * Comparable<? super E>} as a workaround for javac <a
443   * href="http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6468354">bug 6468354</a>.
444   */
445  public static <E extends Comparable<?>> Builder<E> reverseOrder() {
446    return new Builder<>(Ordering.<E>natural().reverse());
447  }
448
449  /**
450   * Returns a builder that creates immutable sorted multisets whose elements are ordered by their
451   * natural ordering. The sorted multisets use {@link Ordering#natural()} as the comparator. This
452   * method provides more type-safety than {@link #builder}, as it can be called only for classes
453   * that implement {@link Comparable}.
454   *
455   * <p>Note: the type parameter {@code E} extends {@code Comparable<?>} rather than {@code
456   * Comparable<? super E>} as a workaround for javac <a
457   * href="http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6468354">bug 6468354</a>.
458   */
459  public static <E extends Comparable<?>> Builder<E> naturalOrder() {
460    return new Builder<>(Ordering.natural());
461  }
462
463  /**
464   * A builder for creating immutable multiset instances, especially {@code public static final}
465   * multisets ("constant multisets"). Example:
466   *
467   * <pre>{@code
468   * public static final ImmutableSortedMultiset<Bean> BEANS =
469   *     new ImmutableSortedMultiset.Builder<Bean>(colorComparator())
470   *         .addCopies(Bean.COCOA, 4)
471   *         .addCopies(Bean.GARDEN, 6)
472   *         .addCopies(Bean.RED, 8)
473   *         .addCopies(Bean.BLACK_EYED, 10)
474   *         .build();
475   * }</pre>
476   *
477   * <p>Builder instances can be reused; it is safe to call {@link #build} multiple times to build
478   * multiple multisets in series.
479   *
480   * @since 12.0
481   */
482  public static class Builder<E> extends ImmutableMultiset.Builder<E> {
483    /*
484     * We keep an array of elements and counts.  Periodically -- when we need more room in the
485     * array, or when we're building, or the like -- we sort, deduplicate, and combine the counts.
486     * Negative counts indicate a setCount operation with ~counts[i].
487     */
488
489    private final Comparator<? super E> comparator;
490
491    @VisibleForTesting E[] elements;
492    private int[] counts;
493
494    /*
495     * The number of used positions in the elements array.  We deduplicate periodically, so this
496     * may fluctuate up and down.
497     */
498    private int length;
499
500    // True if we just called build() and the elements array is being used by a created ISM, meaning
501    // we shouldn't modify that array further.
502    private boolean forceCopyElements;
503
504    /**
505     * Creates a new builder. The returned builder is equivalent to the builder generated by {@link
506     * ImmutableSortedMultiset#orderedBy(Comparator)}.
507     */
508    @SuppressWarnings("unchecked")
509    public Builder(Comparator<? super E> comparator) {
510      super(true); // doesn't allocate hash table in supertype
511      this.comparator = checkNotNull(comparator);
512      this.elements = (E[]) new Object[ImmutableCollection.Builder.DEFAULT_INITIAL_CAPACITY];
513      this.counts = new int[ImmutableCollection.Builder.DEFAULT_INITIAL_CAPACITY];
514    }
515
516    /** Check if we need to do deduplication and coalescing, and if so, do it. */
517    private void maintenance() {
518      if (length == elements.length) {
519        dedupAndCoalesce(true);
520      } else if (forceCopyElements) {
521        this.elements = Arrays.copyOf(elements, elements.length);
522        // we don't currently need to copy the counts array, because we don't use it directly
523        // in built ISMs
524      }
525      forceCopyElements = false;
526    }
527
528    private void dedupAndCoalesce(boolean maybeExpand) {
529      if (length == 0) {
530        return;
531      }
532      E[] sortedElements = Arrays.copyOf(elements, length);
533      Arrays.sort(sortedElements, comparator);
534      int uniques = 1;
535      for (int i = 1; i < sortedElements.length; i++) {
536        if (comparator.compare(sortedElements[uniques - 1], sortedElements[i]) < 0) {
537          sortedElements[uniques] = sortedElements[i];
538          uniques++;
539        }
540      }
541      Arrays.fill(sortedElements, uniques, length, null);
542      if (maybeExpand && uniques * 4 > length * 3) {
543        // lots of nonduplicated elements, expand the array by 50%
544        sortedElements =
545            Arrays.copyOf(sortedElements, IntMath.saturatedAdd(length, length / 2 + 1));
546      }
547      int[] sortedCounts = new int[sortedElements.length];
548      for (int i = 0; i < length; i++) {
549        int index = Arrays.binarySearch(sortedElements, 0, uniques, elements[i], comparator);
550        if (counts[i] >= 0) {
551          sortedCounts[index] += counts[i];
552        } else {
553          sortedCounts[index] = ~counts[i];
554        }
555      }
556      // Note that we're not getting rid, yet, of elements with count 0.  We'll do that in build().
557      this.elements = sortedElements;
558      this.counts = sortedCounts;
559      this.length = uniques;
560    }
561
562    /**
563     * Adds {@code element} to the {@code ImmutableSortedMultiset}.
564     *
565     * @param element the element to add
566     * @return this {@code Builder} object
567     * @throws NullPointerException if {@code element} is null
568     */
569    @CanIgnoreReturnValue
570    @Override
571    public Builder<E> add(E element) {
572      return addCopies(element, 1);
573    }
574
575    /**
576     * Adds each element of {@code elements} to the {@code ImmutableSortedMultiset}.
577     *
578     * @param elements the elements to add
579     * @return this {@code Builder} object
580     * @throws NullPointerException if {@code elements} is null or contains a null element
581     */
582    @CanIgnoreReturnValue
583    @Override
584    public Builder<E> add(E... elements) {
585      for (E element : elements) {
586        add(element);
587      }
588      return this;
589    }
590
591    /**
592     * Adds a number of occurrences of an element to this {@code ImmutableSortedMultiset}.
593     *
594     * @param element the element to add
595     * @param occurrences the number of occurrences of the element to add. May be zero, in which
596     *     case no change will be made.
597     * @return this {@code Builder} object
598     * @throws NullPointerException if {@code element} is null
599     * @throws IllegalArgumentException if {@code occurrences} is negative, or if this operation
600     *     would result in more than {@link Integer#MAX_VALUE} occurrences of the element
601     */
602    @CanIgnoreReturnValue
603    @Override
604    public Builder<E> addCopies(E element, int occurrences) {
605      checkNotNull(element);
606      CollectPreconditions.checkNonnegative(occurrences, "occurrences");
607      if (occurrences == 0) {
608        return this;
609      }
610      maintenance();
611      elements[length] = element;
612      counts[length] = occurrences;
613      length++;
614      return this;
615    }
616
617    /**
618     * Adds or removes the necessary occurrences of an element such that the element attains the
619     * desired count.
620     *
621     * @param element the element to add or remove occurrences of
622     * @param count the desired count of the element in this multiset
623     * @return this {@code Builder} object
624     * @throws NullPointerException if {@code element} is null
625     * @throws IllegalArgumentException if {@code count} is negative
626     */
627    @CanIgnoreReturnValue
628    @Override
629    public Builder<E> setCount(E element, int count) {
630      checkNotNull(element);
631      CollectPreconditions.checkNonnegative(count, "count");
632      maintenance();
633      elements[length] = element;
634      counts[length] = ~count;
635      length++;
636      return this;
637    }
638
639    /**
640     * Adds each element of {@code elements} to the {@code ImmutableSortedMultiset}.
641     *
642     * @param elements the {@code Iterable} to add to the {@code ImmutableSortedMultiset}
643     * @return this {@code Builder} object
644     * @throws NullPointerException if {@code elements} is null or contains a null element
645     */
646    @CanIgnoreReturnValue
647    @Override
648    public Builder<E> addAll(Iterable<? extends E> elements) {
649      if (elements instanceof Multiset) {
650        for (Entry<? extends E> entry : ((Multiset<? extends E>) elements).entrySet()) {
651          addCopies(entry.getElement(), entry.getCount());
652        }
653      } else {
654        for (E e : elements) {
655          add(e);
656        }
657      }
658      return this;
659    }
660
661    /**
662     * Adds each element of {@code elements} to the {@code ImmutableSortedMultiset}.
663     *
664     * @param elements the elements to add to the {@code ImmutableSortedMultiset}
665     * @return this {@code Builder} object
666     * @throws NullPointerException if {@code elements} is null or contains a null element
667     */
668    @CanIgnoreReturnValue
669    @Override
670    public Builder<E> addAll(Iterator<? extends E> elements) {
671      while (elements.hasNext()) {
672        add(elements.next());
673      }
674      return this;
675    }
676
677    private void dedupAndCoalesceAndDeleteEmpty() {
678      dedupAndCoalesce(false);
679
680      // If there was a setCount(elem, 0), those elements are still present.  Eliminate them.
681      int size = 0;
682      for (int i = 0; i < length; i++) {
683        if (counts[i] > 0) {
684          elements[size] = elements[i];
685          counts[size] = counts[i];
686          size++;
687        }
688      }
689      Arrays.fill(elements, size, length, null);
690      Arrays.fill(counts, size, length, 0);
691      length = size;
692    }
693
694    /**
695     * Returns a newly-created {@code ImmutableSortedMultiset} based on the contents of the {@code
696     * Builder}.
697     */
698    @Override
699    public ImmutableSortedMultiset<E> build() {
700      dedupAndCoalesceAndDeleteEmpty();
701      if (length == 0) {
702        return emptyMultiset(comparator);
703      }
704      RegularImmutableSortedSet<E> elementSet =
705          (RegularImmutableSortedSet<E>) ImmutableSortedSet.construct(comparator, length, elements);
706      long[] cumulativeCounts = new long[length + 1];
707      for (int i = 0; i < length; i++) {
708        cumulativeCounts[i + 1] = cumulativeCounts[i] + counts[i];
709      }
710      forceCopyElements = true;
711      return new RegularImmutableSortedMultiset<E>(elementSet, cumulativeCounts, 0, length);
712    }
713  }
714
715  @J2ktIncompatible // serialization
716  private static final class SerializedForm<E> implements Serializable {
717    final Comparator<? super E> comparator;
718    final E[] elements;
719    final int[] counts;
720
721    @SuppressWarnings("unchecked")
722    SerializedForm(SortedMultiset<E> multiset) {
723      this.comparator = multiset.comparator();
724      int n = multiset.entrySet().size();
725      elements = (E[]) new Object[n];
726      counts = new int[n];
727      int i = 0;
728      for (Entry<E> entry : multiset.entrySet()) {
729        elements[i] = entry.getElement();
730        counts[i] = entry.getCount();
731        i++;
732      }
733    }
734
735    Object readResolve() {
736      int n = elements.length;
737      Builder<E> builder = new Builder<>(comparator);
738      for (int i = 0; i < n; i++) {
739        builder.addCopies(elements[i], counts[i]);
740      }
741      return builder.build();
742    }
743  }
744
745  @Override
746  @J2ktIncompatible // serialization
747  Object writeReplace() {
748    return new SerializedForm<E>(this);
749  }
750
751  @J2ktIncompatible // java.io.ObjectInputStream
752  private void readObject(ObjectInputStream stream) throws InvalidObjectException {
753    throw new InvalidObjectException("Use SerializedForm");
754  }
755
756  /**
757   * Not supported. Use {@link #toImmutableSortedMultiset} instead. This method exists only to hide
758   * {@link ImmutableMultiset#toImmutableMultiset} from consumers of {@code
759   * ImmutableSortedMultiset}.
760   *
761   * @throws UnsupportedOperationException always
762   * @deprecated Use {@link ImmutableSortedMultiset#toImmutableSortedMultiset}.
763   * @since 33.2.0 (available since 21.0 in guava-jre)
764   */
765  @DoNotCall("Use toImmutableSortedMultiset.")
766  @Deprecated
767  @SuppressWarnings({"AndroidJdkLibsChecker", "Java7ApiChecker"})
768  @IgnoreJRERequirement // Users will use this only if they're already using streams.
769  @Beta // TODO: b/288085449 - Remove.
770  public static <E> Collector<E, ?, ImmutableMultiset<E>> toImmutableMultiset() {
771    throw new UnsupportedOperationException();
772  }
773
774  /**
775   * Not supported. Use {@link #toImmutableSortedMultiset} instead. This method exists only to hide
776   * {@link ImmutableMultiset#toImmutableMultiset} from consumers of {@code
777   * ImmutableSortedMultiset}.
778   *
779   * @throws UnsupportedOperationException always
780   * @deprecated Use {@link ImmutableSortedMultiset#toImmutableSortedMultiset}.
781   * @since 33.2.0 (available since 22.0 in guava-jre)
782   */
783  @DoNotCall("Use toImmutableSortedMultiset.")
784  @Deprecated
785  @SuppressWarnings({"AndroidJdkLibsChecker", "Java7ApiChecker"})
786  @IgnoreJRERequirement // Users will use this only if they're already using streams.
787  @Beta // TODO: b/288085449 - Remove.
788  public static <T extends @Nullable Object, E>
789      Collector<T, ?, ImmutableMultiset<E>> toImmutableMultiset(
790          Function<? super T, ? extends E> elementFunction,
791          ToIntFunction<? super T> countFunction) {
792    throw new UnsupportedOperationException();
793  }
794
795  /**
796   * Not supported. Use {@link #naturalOrder}, which offers better type-safety, instead. This method
797   * exists only to hide {@link ImmutableMultiset#builder} from consumers of {@code
798   * ImmutableSortedMultiset}.
799   *
800   * @throws UnsupportedOperationException always
801   * @deprecated Use {@link ImmutableSortedMultiset#naturalOrder}, which offers better type-safety.
802   */
803  @DoNotCall("Use naturalOrder.")
804  @Deprecated
805  public static <E> ImmutableSortedMultiset.Builder<E> builder() {
806    throw new UnsupportedOperationException();
807  }
808
809  /**
810   * Not supported. <b>You are attempting to create a multiset that may contain a non-{@code
811   * Comparable} element.</b> Proper calls will resolve to the version in {@code
812   * ImmutableSortedMultiset}, not this dummy version.
813   *
814   * @throws UnsupportedOperationException always
815   * @deprecated <b>Pass a parameter of type {@code Comparable} to use {@link
816   *     ImmutableSortedMultiset#of(Comparable)}.</b>
817   */
818  @DoNotCall("Elements must be Comparable. (Or, pass a Comparator to orderedBy or copyOf.)")
819  @Deprecated
820  public static <E> ImmutableSortedMultiset<E> of(E element) {
821    throw new UnsupportedOperationException();
822  }
823
824  /**
825   * Not supported. <b>You are attempting to create a multiset that may contain a non-{@code
826   * Comparable} element.</b> Proper calls will resolve to the version in {@code
827   * ImmutableSortedMultiset}, not this dummy version.
828   *
829   * @throws UnsupportedOperationException always
830   * @deprecated <b>Pass the parameters of type {@code Comparable} to use {@link
831   *     ImmutableSortedMultiset#of(Comparable, Comparable)}.</b>
832   */
833  @DoNotCall("Elements must be Comparable. (Or, pass a Comparator to orderedBy or copyOf.)")
834  @Deprecated
835  public static <E> ImmutableSortedMultiset<E> of(E e1, E e2) {
836    throw new UnsupportedOperationException();
837  }
838
839  /**
840   * Not supported. <b>You are attempting to create a multiset that may contain a non-{@code
841   * Comparable} element.</b> Proper calls will resolve to the version in {@code
842   * ImmutableSortedMultiset}, not this dummy version.
843   *
844   * @throws UnsupportedOperationException always
845   * @deprecated <b>Pass the parameters of type {@code Comparable} to use {@link
846   *     ImmutableSortedMultiset#of(Comparable, Comparable, Comparable)}.</b>
847   */
848  @DoNotCall("Elements must be Comparable. (Or, pass a Comparator to orderedBy or copyOf.)")
849  @Deprecated
850  public static <E> ImmutableSortedMultiset<E> of(E e1, E e2, E e3) {
851    throw new UnsupportedOperationException();
852  }
853
854  /**
855   * Not supported. <b>You are attempting to create a multiset that may contain a non-{@code
856   * Comparable} element.</b> Proper calls will resolve to the version in {@code
857   * ImmutableSortedMultiset}, not this dummy version.
858   *
859   * @throws UnsupportedOperationException always
860   * @deprecated <b>Pass the parameters of type {@code Comparable} to use {@link
861   *     ImmutableSortedMultiset#of(Comparable, Comparable, Comparable, Comparable)}. </b>
862   */
863  @DoNotCall("Elements must be Comparable. (Or, pass a Comparator to orderedBy or copyOf.)")
864  @Deprecated
865  public static <E> ImmutableSortedMultiset<E> of(E e1, E e2, E e3, E e4) {
866    throw new UnsupportedOperationException();
867  }
868
869  /**
870   * Not supported. <b>You are attempting to create a multiset that may contain a non-{@code
871   * Comparable} element.</b> Proper calls will resolve to the version in {@code
872   * ImmutableSortedMultiset}, not this dummy version.
873   *
874   * @throws UnsupportedOperationException always
875   * @deprecated <b>Pass the parameters of type {@code Comparable} to use {@link
876   *     ImmutableSortedMultiset#of(Comparable, Comparable, Comparable, Comparable, Comparable)} .
877   *     </b>
878   */
879  @DoNotCall("Elements must be Comparable. (Or, pass a Comparator to orderedBy or copyOf.)")
880  @Deprecated
881  public static <E> ImmutableSortedMultiset<E> of(E e1, E e2, E e3, E e4, E e5) {
882    throw new UnsupportedOperationException();
883  }
884
885  /**
886   * Not supported. <b>You are attempting to create a multiset that may contain a non-{@code
887   * Comparable} element.</b> Proper calls will resolve to the version in {@code
888   * ImmutableSortedMultiset}, not this dummy version.
889   *
890   * @throws UnsupportedOperationException always
891   * @deprecated <b>Pass the parameters of type {@code Comparable} to use {@link
892   *     ImmutableSortedMultiset#of(Comparable, Comparable, Comparable, Comparable, Comparable,
893   *     Comparable, Comparable...)} . </b>
894   */
895  @DoNotCall("Elements must be Comparable. (Or, pass a Comparator to orderedBy or copyOf.)")
896  @Deprecated
897  public static <E> ImmutableSortedMultiset<E> of(
898      E e1, E e2, E e3, E e4, E e5, E e6, E... remaining) {
899    throw new UnsupportedOperationException();
900  }
901
902  /**
903   * Not supported. <b>You are attempting to create a multiset that may contain non-{@code
904   * Comparable} elements.</b> Proper calls will resolve to the version in {@code
905   * ImmutableSortedMultiset}, not this dummy version.
906   *
907   * @throws UnsupportedOperationException always
908   * @deprecated <b>Pass parameters of type {@code Comparable} to use {@link
909   *     ImmutableSortedMultiset#copyOf(Comparable[])}.</b>
910   */
911  @DoNotCall("Elements must be Comparable. (Or, pass a Comparator to orderedBy or copyOf.)")
912  @Deprecated
913  // The usage of "Z" here works around bugs in Javadoc (JDK-8318093) and JDiff.
914  public static <Z> ImmutableSortedMultiset<Z> copyOf(Z[] elements) {
915    throw new UnsupportedOperationException();
916  }
917
918  private static final long serialVersionUID = 0xdecaf;
919}